Universal Turing Machine

A Turing machine which, by appropriate programming using a finite length of input tape, can act as any Turing machine whatsoever. In his seminal paper, Turing himself gave the first construction for a universal Turing machine (Turing 1937, 1938). Shannon (1956) showed that two colors were sufficient, so long as enough states were used. Minsky (1962) discovered a 7-state 4-color universal Turing machine, illustrated above (Wolfram 2002, p. 706). Note that the 20th rule specifies that the Turing machine should halt, as indicated by leaving the head stationary and not changing its state. Upon conversion to a 2-color machine, Minsky's universal Turing machine requires 43 states.

Comparatively little more was published about small universal Turing machines until Rogozhin (1996) found examples with the numbers of states and colors given by (24, 2), (10, 3), (7, 4), (5, 5), (4, 6), (3, 10), and (2, 18) (Wolfram 2002, p. 1119).

A 2-state 5-color universal Turing machine, illustrated above, was discovered by Wolfram (2002, p. 707). This example has the smallest product of any other known universal Turing machine. However, there very likely exist examples that are smaller still.

Four 2-state 4-color and 14 essentially equivalent 2-state 3-color machines identified by Wolfram (2002, pp. 708-709) are likely universal, although this appears difficult to prove. On May 14, 2007, Wolfram Research and Stephen Wolfram announced a $25,000 cash prize for a proof that this Turing machine is in fact universal. On Oct. 24, 2007, Alex Smith claimed the prize with a successful proof.

Wolfram Web Resources