A Turing machine which, by appropriate programming using a finite length of input tape, can act as anyTuring
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 (Smith 2020).
Minsky, M. L. "Some Universal Elements for Finite Automata." Automata Studies. Princeton, NJ: Princeton University Press,
pp. 117-128, 1956.Minsky, M. L. "Size and Structure of
Universal Turing Machines Using Tag Systems." Proc. Sympos. Pure Math.5,
229-238, 1962.Ord, T. "Hypercomputation: Computing More Than the
Turing Machine." 25 Sep 2002. http://arxiv.org/abs/math.LO/0209332.Penrose,
R. The
Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics.
Oxford: Oxford University Press, pp. 51-57, 1989.Rogozhin, Yu. V.
"Seven Universal Turing Machines." Mat. Issled., No. 69, 76-90,
1982.Rogozhin, Yu. V. "A Universal Turing Machine with 10
States and 3 Symbols." Izv. Akad. Nauk Respub. Moldova Mat., No. 4,
80-82 and 95, 1992.Rogozhin, Yu. "Small Universal Turing Machines."
Theoret. Comput. Sci.168, 215-240, 1996.Shannon, C. E.
"A Universal Turing Machine with Two Internal States." Automata Studies.
Princeton, NJ: Princeton University Press, pp. 157-165, 1956.Smith,
A. "Universality of Wolfram's 2, 3 Turing Machine." Complex Systems29,
1-44, 2020. Turing, A. M. "On Computable Numbers, with an Application to
the Entscheidungsproblem." Proc. London Math. Soc. Ser. 242,
230-265, 1937. Reprinted in The Undecidable (Ed. M. David). Hewlett,
NY: Raven Press, 1965.Turing, A. M. "Correction to: On Computable
Numbers, with an Application to the Entscheidungsproblem." Proc. London Math.
Soc. Ser. 243, 544-546, 1938.Wolfram Research and Wolfram,
S. "The Wolfram 2,3 Turing Machine Research Prize." http://www.wolframscience.com/prizes/tm23/.Wolfram,
S. A
New Kind of Science. Champaign, IL: Wolfram Media, pp. 706-711
and 1119, 2002.
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).
of any other known universal Turing machine. However,
there very likely exist examples that are smaller still.
