[FOM] 2,3 Turing machine proof controversy

[Vaughan Pratt]

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