Technical Commentary
The s=2, k=3 Turing machine 596440 has been demonstrated to be universal by Alex Smith, who constructed a sequence of rule systems that shows the Turing machine is capable of arbitrary finite computations and used a novel approach to extend that construction to unbounded computations. Here we outline his proof. Further details about the proof can be found in Smith's prize-winning submission. For definitions of terms in what follows, as well as background, etc., see the technical details.
The proof proceeds in two stages. The first part demonstrates an emulation of any finite evolution of any two-color cyclic tag system. This emulation is the composition of a series of emulations between rule systems called system 1 through system 5, each one emulating the next.
The lemmas needed to prove these emulations follow from a detailed study of the action of the Turing machine on blocks of zero-free sequences Zi. In particular, between the time the active cell enters Z and the time it exits Z, the transformation of the region Z has useful properties that can be easily demonstrated.
To give a flavor for the very detailed argument, what follows are a few facts concerning the three-state (A, B, C) three-color generalized Turing machine called system 3. Restricting the construction to regions that are a power of 2 in length and when the initial condition is in state A, three functions are introduced, called scan, parity, and state parity:
scan(Z,n)=the state of the sequence when the active head is at the first position in Z for the nth time in state B or C.
parity(Z)=|{0 or 2 in Z}| mod 2
s(n)= 0 if at the time of the nth scan the state at the first position in Z is B, 1 if the state at the first position in Z is C
p(n)= parity of scan n
He then proves lemma 1, where 2w is the length of Z, and n>2w,
1. p(n)=p(n-2w)+s(n-2w) (mod 2).
2. If p(n)+s(n)=0 (mod 2) at scan n, then the next time the element to the right of the set becomes active it will be active in state B. Otherwise, that element will be active in state A if it is a 0 or state C if it is not.
3. At each scan, all elements of the set will be either 1 or 2.
With these and other properties, Smith is able to show the existence of useful sequences on the tape for his constructions. Additionally, he notes that their construction can be done efficiently using rule 60, which is computationally reducible.
When particular zero-free sequences are part of a larger ensemble, the dynamics of the scans' parities emulate the fourth system in Smith's construction. That system is number-based, as is the fifth system. The fifth system is suitable for emulating any two-color cyclic tag system, but only for a finite number of steps. To complete the proof of universality, the second part must be shown: that it can emulate an unbounded computation.
Through concrete considerations, it is shown that these finite calculations can be concatenated in the initial condition, so an unbounded computation can be realized by performing step 1, then step 0, followed by steps 1 and 2, then back to step 0 followed by steps 1, 2, and 3, and so on. Smith defines and analyzes a procedure that doubles the number of steps in an cyclic tag emulation, the limit of which provides the initial condition for unbounded computation. The procedure that doubles an initial condition has a recursive form:
Init[2n]=Init[n] + F[Init[n],n,k]
It is shown that even though the initial condition is not repetitive, the process defined by F is clearly not universal, in analogy to the construction of the Thue-Morse sequence. The Turing machine 596440 is therefore universal.
More About the Prize » | More About the Solution »