[FOM] 2,3 Turing machine proof controversy
Vaughan Pratt
pratt at cs.stanford.edu
Sun Nov 11 15:29:42 EST 2007
I should give a bit more detail about my line of thought with
> While I agree in principle with Bob that there's a question even about
> periodic "background", this bothers me less because with a few more
> states a Turing machine can generate such a background on its own. To
> my thinking all that a periodic background accomplishes is to feed a few
> steroids to the Turing machine without however converting a
> non-universal machine (in some "moral" sense) into a universal one.
The generation of periodic background requires only O(1) storage, which
can all fit inside the Turing machine's state, allowing any periodic
background to be generated in a single pass. But there is no need to
actually generate it since the Turing machine can with the extra states
it would have needed to write it merely hallucinate it instead as it
goes about its other business. So allowing a periodic background can
only save a few states, it cannot actually increase the power of the
basic Turing machine architecture.
Any nonperiodic pattern however cannot be hallucinated in this way: the
Turing machine has no alternative to using the tape as storage in order
to generate a nonperiodic background, and moreover no constant bound can
be put on the amount of tape so needed (otherwise the pattern would have
been periodic). This is true even for something so apparently simply as
writing RXRXXRXXXRXXXXR... It must tediously copy a preceding block of
X's to the next block, a fixed finite number of X's at a time (one X at
a time for simplicity), going back and forth to do so, and then
appending one more X in order to make the next block one larger.
Once you start letting an initialization process make such nontrivial
use of storage one can no longer use the argument that background
information adds nothing. Since we had to use Turing machine tape, even
if in a seemingly trivial way, that is a form of outside help that could
potentially convert a nonuniversal machine into a universal one. In
Alex's application it is like equipping the basic machine with a counter
that it did not have before.
The stronger objection can be raised that even the implicit addition of
finitely many (O(1)) extra states to the control by providing a periodic
background is already taking too much of a liberty with the definition
of "universal" for Turing machines. Again I'm not the judge here and
would not want to argue this one either way. But when things like
implicit counters are added I start to get more agitated.
Since my previous puzzle as to whether disallowing writing 0 inhibited
universality for 2-symbol TM's was so easy, here's another. What is the
least m for which universality is possible for a 2-symbol Turing machine
with one tape and three heads all constrained to move only right, such
that m heads can write 0 and 1 (as well as read) and the remaining 3-m
heads are read-only (each such head can write neither 0 or 1 but can
only see what's on the cell it is on)? I'll be happy to collect votes
for m and report on their mean and variance. :)
Vaughan
More information about the FOM
mailing list