[FOM] 2,3 Turing machine proof controversy
Vaughan Pratt
pratt at cs.stanford.edu
Sun Nov 18 01:00:33 EST 2007
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
More information about the FOM
mailing list