[FOM] 2,3 Turing machine proof controversy
Vaughan Pratt
pratt at cs.stanford.edu
Tue Nov 13 01:28:10 EST 2007
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;
This is an example of where something "obviously" non-universal is
actually universal. Here's how to see that a 2-symbol Turing machine
that cannot write 0 can be universal.
Divide the tape into three-cell blocks. Each block could in principle
have any of 2^3 = 8 states, but we'll only use four, namely 000, 100,
110, and 111. The initial input is a finite pattern of the form
111110100100100... (one 111 block, one 110 block, one or more 100
blocks) and the rest of the tape is blank (000 blocks). All writes to
the tape can be described as one of three possible block transitions:
000 -> 100, 100 -> 110, or 110 -> 111. Each of these transitions is
accomplished by writing a 1; there is never any need to write 0.
At all times the tape is divided into four regions, namely a region of x
111 blocks starting at cell 0, then a region of y 110 blocks starting at
cell 3x, then a region of z 100 blocks starting at cell 3(x+y), and the
rest of the tape starting at cell 3(x+y+z) is blank. For example if x =
2, y = 4, z = 3 then the tape is
111111110110110110100100100000000000...
The machine is started with x = y = 1 and z indefinite (the input). For
simplicity of defining region boundaries we shall arrange to keep x, y,
and z nonzero at all times.
We will arrange for this machine to only move the region boundaries to
the right.
* To move the 100000 boundary right, change it to 100100.
* To move the 110100 boundary right, change it to 110110 (but if that
would leave no 100 block, i.e. we are about to change 110100000 to
110110000, first move the 100000 boundary right by the preceding procedure).
* To move the 111110 boundary right, change it to 111111 (but if that
would leave no 110 block, i.e. we are about to change 111110100 to
111111100, first move the 110100 boundary right by the preceding procedure).
This machine can simulate a two-counter machine, with z-1 and y-1 as the
counter values. Initially the counters are set to z-1 and 0. The
procedure above for keeping y and z nonzero ensures that no counter can
be driven negative in the event that the machine attempts to decrement a
zero counter. We need to simulate test-for-zero (z==1 or y==1),
increment (z++ or y++), and decrement (z-- or y--), accomplished as follows.
z==1 Only one 100 block remaining.
y==1 Only one 110 block remaining.
z++ Move 100000 boundary right
y++ Move 100000 and 110100 boundaries right
z-- Move 110100 and 111110 boundaries right
y-- Move 111110 boundary right
Two-counter machines are universal and hence so are machines that can
only write 1 and not 0, via the above simulation.
Vaughan Pratt
More information about the FOM
mailing list