 History [of universal Turing machines]
Alan Turing gave the first construction for a universal Turing machine in 1936. His construction was complicated and had several bugs. Claude Shannon showed in 1956 that 2 colors were sufficient so long as enough states were used. (See page 669; conversion of Minsky's machine using this method yields a {43, 2} machine.) After Minsky's 1962 result, comparatively little more was published about small universal Turing machines. In the 1980s and 1990s, however, Yurii Rogozhin found examples of universal Turing machines for which the number of states and number of colors were: {24,2}, {10,3}, {7, 4}, {5,5}, {4,6}, {3,10}, and {2,18}. The smallest product of these numbers is 24 (compare note below), and the rule he gave in this case is:
Note that these results concern Turing machines which can halt (see page 1137); the Turing machines that I consider do not typically have this feature.
|
 |
|
PAGE IMAGE
|
