Universal Turing machines
There's been some interesting discussion over on the computational complexity blog about Wolfram's problem of determining whether a particular Turing machine with 2 states and 3 symbols is universal, a problem he's offering $25,000 to solve. The CC blog discussion has largely been on what makes a problem like this one interesting or not interesting. My own response is that I'm not terribly excited by the problem of finding minimum Turing machines, because I think the Turing machine model itself is a bit inelegant, but that the search for a proof for this problem could still lead to some interesting techniques. I do have some additional connection to the problem, though, which I think may still be of some interest at this late date.
To begin with, characteristically, Wolfram's page on the prize problem miscredits the past results. It says that the best previous universal TM, a machine with 2 states and 5 symbols, was found by Wolfram himself, and published in A New Kind of Science, but my understanding is that the actual discovery was by Wolfram employee Matthew Cook, in 1998, who was then sued by Wolfram for violation of nondisclosure when he attempted to publish his results. Cook actually found four machines, with (states,symbols) = (8,2), (4,3), (3,4), and (2,5), all based on simulating the Rule 110 cellular automaton. However, traditional universal Turing machines, when simulating some other computation, halt when the simulated computation halts and avoid halting when the simulated computation fails to halt; none of Cook's machines ever halts, so describing the situation that corresponds to a halt of the simulated computation is nontrivial. In addition, unlike traditional universal machines, simulating other computations on Cook's machines requires that the starting configuration of the tape have infinitely many non-blank cells.
If one accepts machines of this type as universal, the only one that would not be made obsolete as a smallest-possible universal TM by Wolfram's new (2,3) machine would be the (8,2) one. But, unlike the others, that one was made obsolete almost as soon as Cook described his results. I copy below my email from 1998 describing a (7,2) simulator for Rule 110, heavily based on another of Cook's machines.
Message-ID: <13940.8670.447381.773516@euclid.ics.uci.edu>
From: David Eppstein <eppstein@ics.uci.edu>
To: Matthew Cook <cook@mail.datanet.hu>
Subject: Re: New CA universality theorem: 110 is universal (Cook)
Date: Sun, 13 Dec 1998 12:21:50 -0800 (PST)
Matthew Cook writes:
> 3 States, 4 Symbols
> Symbols: dry black, dry white, fresh black, fresh white
> States: saw W, saw WB, saw BB
> Idea: Move to the right doing Rule 110, converting dry black and white
> to fresh black and white. When we bump into something fresh, we
> bounce back to the left, drying all the paint as we go.
> Eventually we will arrive at paint that was already dry, so we
> start the cycle over again.
> The initial conditions are a central area of dry paint, with the
> head at the left. On the left hand side is mostly wet paint,
> with an occasional dry cell (like the "bounce" symbols in the
> previous machine), and on the right hand side is mostly dry
> paint, with an occasional wet cell (also like the "bounce"
> symbols in the previous machine).
I think this can be converted to a 7 state 2 symbol machine:
Symbols: wet/dry in even positions, black/white in odd positions.
Each symbol should be thought of as a composite (dryness,color).
States: saw W, saw WB, saw BB, to W, to WB to BB, copy
Idea: a state with the same name as the 3x4 machine looks at the color
of a pair that's just been turned wet. It then makes a transition
to "to something". A state "to something" expects to see a dry cell,
turns it wet, and goes to state "saw something". But if "to W"
sees a wet cell, it goes into the bouncing left mode, where it
dries the cell and enters a special copy state.
Transition Table:
Read v In > saw W saw WB saw BB copy
------ ------------ ------------ ------------- -------------
black B, to WB, R B, to BB, R W, to BB, R B, to W, L
white W, to W, R B, to W, R B, to W, R W, to W, L
Read v In > to W to WB to BB
------ ------------ ------------ ------------
dry W, saw W, R W, saw WB, R W, saw BB, R
wet D, copy, L W, saw WB, R W, saw BB, R
--
David Eppstein UC Irvine Dept. of Information & Computer Science
eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/
At the time, I sent this description to a few mailing lists; I think it can still be found in Google groups. But it has never been formally published, in part because I'm not convinced that a one-state improvement on Cook's (8,2) machine is a significant accomplishment, in part at the time out of courtesy to Cook to let him publish first (which he never did due to Wolfram's suit). If Wolfram's problem has a positive solution, this (7,2) machine and Wolfram's (2,3) machine would be the two smallest known (nontraditional) universal TMs.