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. Shannon showed that two colors were sufficient, so long as enough states were used. Minsky discovered a 7-state 4-color universal Turing machine, illustrated above. 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.

Chaitin's constant | halting problem | Turing machine | universal cellular automaton | universality