[seqfan] Re: Post's tag system

[Neil Sloane]

Let me say a bit more about Post tag system and the Curling Number Conjecture.

Post's tag system maps a word w over {0,1} to w', where if w begins
with 0, w' is obtained by appending 00 to w and deleting the first
three letters, or if w begins with 1, w' is obtained by appending 1101
to w and deleting the first three letters.

If you start with a binary word w and repeatedly apply this map, one
of 3 things will happen. The orbit of a word may terminate at the
empty word (see A289670 and A289675), or enter a cycle (A289671,
A289672, A289674), or grow without limit (it is not known if this ever
happens, as Allan W. has pointed out). See A284116 and A289670-A289675
for further information.  Don Reble has provided a Python program, see
A289670.

On the other hand, if you start with a word over {2,3} and repeatedly
append the curling number, one of 2 things will happen: Eventually the
curling number appended will be 1, when we stop, or the curling number
will be 2 or 3 for ever (it is not known if this ever happens; the
conjecture is that it does not).  See A094004 for the records for how
long an initial string of 2s and 3s can survive without reaching a 1.
(Cycles can occur, but a cycle will immediately lead to curling number
1.)

There are some similarities between the graphs of A284116 and A094004. It would
be nice to have more terms for all these sequences. Is the connection
between the Post problem and the Curling Number problem anything more
than a coincidence? In both problems we are looking for binary words
with long orbits.

Best regards
Neil

Neil J. A. Sloane, President, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com



On Sat, Jul 29, 2017 at 9:41 PM, Allan Wechsler <acwacw at gmail.com> wrote:
> Tag automata in general are known to be computationally universal. Post's
> example (0xx -> 00; 1xx -> 1101) looks very chaotic and could in principle
> turn out to be universal; Marvin Minsky on occasion speculated that it very
> well might be, though he went back and forth on the subject during his
> life. John Conway investigated a very similar automaton (0xx -> 00; 1xx ->
> 1011), which he called "Oo-Bobb". He may have been under the impression
> that this was in fact Post's machine. There are some deep links between the
> two versions, and I suspect that if one is universal, so is the other.
>
> If Post's tag automaton is universal, it must have a starting string whose
> orbit grows without limit. No such starting string is currently known (at
> least, none were known the last time I investigated the subject, around 15
> years ago). This is why the definition includes the word "finite",
> specifically excluding starting strings with infinite, nonrepeating orbits.
>
> The existence of an infinite, nonrepeating orbit in Post's tag automaton
> would be an important research result.
>
> On Sat, Jul 29, 2017 at 7:05 PM, Neil Sloane <njasloane at gmail.com> wrote:
>
>> Post's tag system is described in A284116.  (I learned about it from
>> reading John Stillwell's wonderful book "Elements of Mathematics: From
>> Euclid to Goedel", Princeton, 2016). There are some vague similarities
>> between the Post tag construction and the Curling Number Conjecture
>> (see arXiv:1212.6102), which might give a hint as to why the latter has
>> proved so intractable.
>>
>> In particular, the known terms of A284116 are a bit similar to those of
>> A094004 (compare the two graphs), so it would be interesting to
>> have a lot more terms of the former sequence, in case people would like to
>> help
>>
>> It would be nice also to have a lot more terms for the other sequences
>> related to Post tag systems that I added today (A289670-A289674).
>>
>> Rather than trying to prove the Curling Number Conjecture, maybe it would
>> be easier to show it is equivalent to one of the unsolvable problems
>> (studied by Post, Turing, ...) in the field of computability!  ("I can't
>> solve the problem, so instead I'll show that the problem is insoluble".)
>>
>> By the way, my Maple program in A289670 is very naive, and I included it
>> merely to show how I found the terms.
>> All of these entries - especially A284116 - could use high-quality programs
>> - and a lot more terms.
>>
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/