[FOM] 2,3 Turing machine proof controversy

[Todd Rowland]

On Mon, 19 Nov 2007, Bob Hearn wrote:

>> [Minsky writes]
>>
>> In any case, I still would like to know if Post's original 3-Tag
>> system is universal in any sense.  That's the one with the two
>> productions:
>>
>>  0 X X [string] -->  [string] 0 0
>>  1 X X [string] -->  [string] 1 1 0 1
>>
>> because I regard that as the simplest known unsolved machine.
>
> Minsky last seriously studied this problem in the 60s. I wonder
> whether anyone has had a go at it recently? To my knowledge, it's
> still not even known whether there are any initial strings that grow
> indefinitely.

We investigated Post's tag system at the NKS summer school (June 2007) as 
one of our live experiments.

It seems like every initial condition becomes eventually periodic although 
the transients can be interesting.  It seems that many things about this 
rule are interesting, including its periodic configurations.

The good news is that during the live experiment Stephen Wolfram found 
what is possibly the smallest tag system that is universal.

{0,_,x___}->{x,0,1}
{1,_,x___}->{x,1,0,0}

You can read more at

http://blog.wolfram.com/2007/07/science_live_and_in_public.html

which describes the discovery.

Even if Post's tag system is not the smallest universal one, it has more 
than historical interest.  Can one prove it is ultimately periodic?  What 
tools are needed?