[FOM] 2,3 Turing machine proof controversy
Vaughan Pratt
pratt at cs.stanford.edu
Tue Nov 13 04:33:03 EST 2007
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
More information about the FOM
mailing list