[seqfan] Re: Post's tag system

[Allan Wechsler]

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/
>