Editing Universal Turing machine (section)

==Smallest machines==
When Alan Turing came up with the idea of a universal machine he had in mind the simplest computing model powerful enough to calculate all possible functions that can be calculated. [[Claude Shannon]] first explicitly posed the question of finding the smallest possible universal Turing machine in 1956. He showed that two symbols were sufficient so long as enough states were used (or vice versa), and that it was always possible to exchange states for symbols. He also showed that no universal Turing machine of one state could exist.

[[Marvin Minsky]] discovered a 7-state 4-symbol universal Turing machine in 1962 using [[tag system|2-tag systems]]. Other small universal Turing machines have since been found by Yurii Rogozhin and others by extending this approach of tag system simulation. If we denote by (''m'', ''n'') the class of UTMs with ''m'' states and ''n'' symbols the following tuples have been found: (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9), and (2, 18).{{sfnp|Rogozhin|1996}}{{sfnp|Kudlek|Rogozhin|2002}}{{sfnp|Neary|Woods|2009}} Rogozhin's (4, 6) machine uses only 22 instructions, and no standard UTM of lesser descriptional complexity is known.

However, generalizing the standard Turing machine model admits even smaller UTMs. One such generalization is to allow an infinitely repeated word on one or both sides of the Turing machine input, thus extending the definition of universality and known as "semi-weak" or "weak" universality, respectively. Small weakly universal Turing machines that simulate the [[Rule 110]] cellular automaton have been given for the (6, 2), (3, 3), and (2, 4) state-symbol pairs.{{sfnp|Neary|Woods|2009b}} The proof of universality for [[Wolfram's 2-state 3-symbol Turing machine]] further extends the notion of weak universality by allowing certain non-periodic initial configurations. Other variants on the standard Turing machine model that yield small UTMs include machines with multiple tapes or tapes of multiple dimension, and machines coupled with a [[finite automaton]].