[FOM] 2,3 Turing machine proof controversy

[Vaughan Pratt]

The basic question with Alex Smith's proof is whether his nonperiodic 
initial condition is just as harmless as the periodic condition 
generally accepted as harmless by the NKS (New Kind of Science) 
community or can provide enough assistance to convert a nonuniversal 
machine into a universal one, which would seem not in the spirit of the 
prize.  (Initializing the tape to say Chaitin's Omega would surely not 
be in that spirit.)

The following exchange suggests an abstraction of Alex Smith's 
nonperiodic initial condition to something simple enough to analyze 
directly.

AS> Imagine the following input:
 >
 > ...__R0110_01X_R0110_01XX_110XX_R0110_01XXX_110XXX_01XXX_R...
 >
 > This input tells the system to emulate the cyclic tag system for one
 > step, then two steps, then three steps, then so on. The input to this
 > system isn't periodic, but is simple to construct in a non-universal
 > way. Is this Turing machine universal?

VP> Let's say it's at least less objectionable than a machine that has
 > to be repeatedly restarted "manually" (deus ex machina).

My LBA-based objection to Smith's proof assumed manual restarting. 
Smith's rebuttal as I understand it is that his emulation involves no 
restarting.  Instead the tape is initialized at the beginning to a 
recursively (or at least iteratively) defined infinite initial condition 
and then allowed to run on that tape without interruption.  Here it's 
less clear how my LBA-based objection should work since there's no 
obvious measure of input length to base it on.  One could make one up, 
e.g. by taking the distance between consecutive R's, but that measure 
seems somewhat arbitrary and therefore hard to justify.

This raises the question of whether there is some more compelling 
situation where a nonperiodic initial condition of this simple kind can 
convert nonuniversal into universal machines.

Consider the following three kinds of initial condition for the Turing 
machine tape, which I'll assume here is infinite in both directions and 
hence indexed by the integers, and has only two symbols, 0 and 1, which 
I'll call white and black following the NKS community's custom of 
referring to symbols as colors.

P: Periodic, meaning that there exists n > 0 such that for all integers 
i the i-th cell and the (i+n)-th cell are the same color.

Z: Cell 0 is black and the rest of the tape is white.

T: Cells indexed by the triangular numbers (0, 1, 3, 6, 10, ..., 
n(n+1)/2, ...) are black and the rest are white.  This is intended as a 
clean abstraction of (my undertanding of) Smith's initial condition.

In order to maintain the integrity of these tape patterns, confine 
attention to read-only Turing machines.  Even with blank tape, three 
read-only heads 0,1,2 that can tell when two heads are on the same cell 
suffice for universal computation because they can emulate a two-counter 
machine by representing each counter as the distance between the i-th 
and (i+1)-st head for i = 0,1.  (This makes m = 0 the answer to a puzzle 
I posed a couple of days ago about machines with three heads m of which 
could write.)

Periodic tapes do not add anything to blank tapes, at least when the 
period n is given a priori, as a Turing machine with n^2 states can 
"hallucinate" any given periodic pattern of periodicity n.  It follows 
that tapes initialized to a periodic background may permit some 
economization of states but cannot make a class of nonuniversal machines 
universal unless the class is defined in terms of a limit on the number 
of states.  (For example the class of Turing machines with at most 2 
states might have no universal members unless infinite periodic initial 
conditions are allowed, which I understand to be the point of allowing 
this sort of tape initialization.)

These considerations suggest the following formulation of the problem. 
Is there a class of Turing machines that imposes no limit on the number 
of states, such that no machine in that class is universal for initial 
conditions of type P or Z but for which there exists a machine which is 
universal for the initial condition T (triangular black cells)?

Take the class I to consist of Turing machines with two Independent 
read-only heads each capable of reading the tape cell it is on but not 
capable of recognizing when both heads are on the same tape cell.  (The 
prize concerns a one-headed machine, which however is permitted to write 
and hence can simulate multiheaded read-only machines; hence an n-headed 
read-only machine can be understood as a subclass of the class of 
1-headed read-write machines.)  Let W (for "whitelocked") be the 
subclass of T constrained to hold the average head position constant 
(equivalently the heads must move in opposite directions) when both 
heads are scanning a white cell.  Whereas two independent heads may be 
able to emulate two counters, whitelocking them may inhibit that ability.

I claim that the following combinations of head constraints and initial 
conditions admit either only Nonuniversal or some Universal machines.

.   | P  Z  T
----+--------
. I | N  U  U
. W | N  N  U

That is, universal machines are impossible for periodic tapes, with or 
without the whitelocking condition.  With triangular tapes however 
universal machines are possible even with whitelocking.  In between, for 
tapes with one black cell, if the heads are independent it becomes 
possible to emulate a two-counter machine but not if the heads are 
whitelocked.

This table makes the point first of all that the situation is even worse 
than with triangular tapes.  Although periodic tapes are harmless, a 
tape that is nonperiodic by virtue of having exactly one black cell is 
already enough to convert an otherwise nonuniversal machine into a 
universal one.

Since semi-infinite tapes (those indexed by the natural numbers rather 
than by the integers) are commonly used, one might worry that the class 
I fails to distinguish the natural boundary of a semi-infinite tape from 
the kind of pattern Smith proposes.  Whitelocking the two heads 
addresses this by reducing the machine to essentially a one-counter 
machine on the tape Z.  On the tape T however it becomes possible to 
emulate two counters (nice exercise).

Vaughan Pratt