[FOM] 2,3 Turing machine proof controversy
pratt at cs.stanford.edu
Wed Nov 14 12:09:54 EST 2007
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.)
More information about the FOM