[FOM] 2,3 Turing machine proof controversy

[Bob Hearn]

Thanks to Vaughan (whom I've never met) for his kind introduction.


On Nov 17, 2007, at 10:00 PM, Vaughan Pratt wrote:

> I agree with both Hearn and Neary and Woods, the common element of  
> which
> might be summarized as, incomparable conventions for small Turing
> machines yield incomparable results.

Speaking of small computing machines, and at the risk of contradicting  
myself that the notion is ill-defined, I was discussing this issue  
with Minsky, and he remarked that:

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


Back to Vaughan:

> Regarding Neary's point,
>
>> An objection that can be made to Kleine-Buning and
>> Ottmann's machine is that using a 2-dimensional tape is
>> unreasonable. In my opinion this is a much less a
>> contentious issue than Smith's (interesting) encoding.
>
> I would argue the opposite, namely that a 2-dimensional tape is in  
> fact
> slightly *more* objectionable than Smith's initialization.  ...
>
> This is because such a machine can simulate a two-counter machine.

Incidentally, the reduction chain from arbitrary Turing machines to  
cyclic 2-tag systems to Wolfram's (2,3) machine proceeds via two- 
counter machines.

Bob Hearn