[FOM] 2,3 Turing machine proof controversy

[Vaughan Pratt]

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.

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.  Assume a 
semi-infinite tape (which in the two-dimensional case becomes the upper 
right quadrant), such that the Turing machine can recognize when it is 
at the beginning (the boundary in the case of two dimensions).  Assume 
nothing about how the tape is initialized (all blank or garbage as you 
prefer).  Then there exists a universal Turing machine (with a single 
head as usual) that only reads and never writes.  (Or equivalently, one 
with a one-symbol tape alphabet.)

This is because such a machine can simulate a two-counter machine.  The 
two counters are represented by the x,y coordinates of the head. 
Incrementing and decrementing counters is accomplished by moving the 
head right or left for x and up or down for y.  When decrementing a 
counter, reaching the boundary corresponds to that counter becoming 
zero.  Except for the boundary itself the tape content is immaterial, 
only the position of the head.  (The initial head position suffices to 
encode the input.)

Had the tape been the whole plane (no boundaries) and initialized to all 
blank cells, such a Turing machine would amount to a finite state 
machine with (in effect) no input, clearly not universal.  A boundary 
(or explicitly drawn X and Y axes on an otherwise blank plane) is all it 
takes to make this otherwise finite-state machine universal.

Smith's encoding seems to require a slightly less trivial machine, for 
example the Turing machine with two read-only "white-locked" heads I 
suggested earlier.  With only one read-only head I didn't see how to get 
the universality provided by a two-dimensional tape, two white-locked 
heads was as close as I could get to a single head.  On that basis I 
would judge Smith's initialization of a one-dimensional tape to be less 
objectionable than a two-dimensional blank tape (but only slightly so).

The participants in this competition seem to be unwilling to acknowledge 
the ability of very slight modifications to the definition of Turing 
machine to turn nonuniversal machines into universal.  In particular the 
ability to count has been casually dismissed by both Smith and the 
judges as being so far from universal as to contribute only negligibly 
to universality.  Now it is certainly true that no one-counter machine 
can be universal.  However any initial condition or other capability 
that can be shown to furnish such a nonuniversal machine with a second 
counter makes possible a universal Turing machine.

This only amplifies the importance attached by Hearn and Neary and Woods 
to adhering to the established conventions, since even seemingly 
innocent departures can easily render the results meaningless.

Vaughan Pratt