[FOM] 2,3 Turing machine proof controversy

[Vaughan Pratt]

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