[FOM] 2,3 Turing machine proof controversy
Todd Rowland
rowland at wolfram.com
Tue Nov 20 19:59:17 EST 2007
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?
More information about the FOM
mailing list