Wolfram's 2-state 3-symbol Turing Machine - Proof of Universality

Proof of Universality

On 24 October 2007, it was announced by Wolfram Research (without the approval of the judging committee ) that Alex Smith, a student in electronics and computing at the University of Birmingham (UK), proved that the (2,3) Turing machine is universal and thus won Wolfram's prize described above. Martin Davis, a member of the committee, noted in a post to the FOM mailing list that:

"As far as I know, no member of the committee has passed on the validity of this 40 page proof. The determination that Smith's proof is correct seems to have been made entirely by the Wolfram organization. My understanding is that the I/O involves complex encodings."

The proof showed that the machine is equivalent to a variant of a tag system already known to be universal. Smith first constructed a sequence of rule systems showing that the (2,3) Turing machine is capable of arbitrary finite computations. He then employed a novel approach to extend that construction to unbounded computations. The proof proceeds in two stages. The first part emulates the finite evolution of any two-color cyclic tag system. The emulation is a composite of a series of emulations involving the indexed rule systems 'system 0' through 'system 5'. Each rule system emulates the next one in the sequence. Smith then showed that even though the initial condition of the (2,3) Turing machine is not repetitive, the construction of that initial condition is not universal. Hence the (2,3) Turing machine is universal.

Vaughan Pratt disputed the correctness of this proof in a public list of discussion, noting that similar techniques would allow a linear bounded automaton (or LBA) to be universal, which would contradict a known non-universality result due to Noam Chomsky. Alex Smith joined the mailing list after this message and replied on the following day explaining that a LBA would require to be restarted manually to become universal using the same initial configuration, while his construction restarts the Turing machine automatically with no external intervention. Discussions about the proof continued for some time between Alex Smith, Vaughan Pratt, and others.

Wolfram claims that Smith's proof is another piece of evidence for Wolfram's general Principle of Computational Equivalence (PCE). That principle states that if one sees behavior that is not obviously simple, the behavior will correspond to a computation that is in a sense “maximally sophisticated”. Smith's proof has unleashed a debate on the precise operational conditions a Turing machine must satisfy in order for it to be candidate universal machine.

A universal (2,3) Turing machine has conceivable applications. For instance, a machine that small and simple can be embedded or constructed using a small number of particles or molecules. But the “compiler” Smith's algorithm implies does not produce compact or efficient code, at least for anything but the simplest cases. Hence the resulting code tends to be astronomically large and very inefficient. Whether there exist more efficient codings enabling the (2,3) Turing machine to compute more rapidly is an open question.