[FOM] 2,3 Turing machine proof controversy

[Robert Smith]

Vaughn Pratt's example of a TM that is universal but is forbidden to write a
0 is questionable.

As can be seen from the definition below, the machine works by assuming that
the tape is initialized to "blanks" in the form of 0's.  Basically, you only
write when you want a 1, otherwise you leave it the 0 that was already
there.  The proposed encoding allows you to do this.


VP> For example could a Turing machine with tape alphabet
VP> {0,1} be universal if it is forbidden to write 0?  Surely the tape would
VP> fill up with ones making universality impossible.  Nice puzzle.

AS> This is an obviously non-universal method of initialising the tape;

VP> This is an example of where something "obviously" non-universal is
VP> actually universal.  Here's how to see that a 2-symbol Turing machine
VP> that cannot write 0 can be universal.

VP> Divide the tape into three-cell blocks.  Each block could in principle
VP> have any of 2^3 = 8 states, but we'll only use four, namely 000, 100,
VP> 110, and 111.  The initial input is a finite pattern of the form
VP> 111110100100100... (one 111 block, one 110 block, one or more 100
VP> blocks) and the rest of the tape is blank (000 blocks).

I have always believed that the correct formulation of "blank" was
"unreadible" or perhaps "garbage" but that (except for an initial finite
portion with data) the arbitrarily long tape should not be assumed to have
any useful data on it at all.

The situation is reminiscent of programming languages like C that typically
do not initialize the space allocated (on the stack or the heap with
malloc).  The user is expected to perform an explicit initialization (which
I consider good programming form even in higher-level languages that perform
automatic initialization).  Just because you are leaving it to the runtime
system to perform the initialization doesn't mean that it isn't being done
someplace.  In the case of this TM, whoever has set it up has provided an
infinite supply of zero's!

In a way (but not completely), this is a similar problem to the questions
about the Wolfram prize machine, to me at least.


Bob Smith
Stanford