[FOM] 2,3 Turing machine proof controversy

[Vaughan Pratt]

Robert Smith wrote:
> 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.

Not true.  It only assumes a single 000 block at the end of the input, 
without which there would be no way of recognizing the end of the input 
(the garbage might happen to start 100100100000...)  Moreover my 
emulation does not depend on there being two 000 blocks at the end at 
any stage, and the process of promoting the one 000 block at the end to 
100 entails appending a new 000 block beyond it, which works regardless 
of what garbage used to be there.

> 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.

While this is a good point of view, for the purpose of defining 
universality it is fully compatible with the alternative of requiring 
the rest of the tape to be blank, as the Turing machine can always 
initialize garbage tape to blank tape when it comes to the end of the 
known tape.  (A machine that can't recognize the end of the known tape 
is at risk of mistaking garbage for known tape.)

Vaughan Pratt