Notes

Chapter 11: The Notion of Computation

Section 12: Universality in Turing Machines and Other Systems


Minsky's [universal] Turing machine

The universal Turing machine shown was constructed by Marvin Minsky in 1962. If the rules for a one-element-dependence tag system are given in the form {2, {{0,1},{0,1,1}}} (compare page 1114), the initial conditions for the Turing machine are

TagToMTM[{2, rule_}, init_] := With[{b = FoldList[Plus, 1, Map[Length, rule]+1]}, Drop[Flatten[{Reverse[Flatten[ {1, Map[{Map[{1, 0, Table[0, {b[[#+1]]}]}&, #], 1}&, rule], 1}]], 0, 0, Map[{Table[2, {b[[#+1]]}], 3}&, init]}], -1] ]

surrounded by 0's, with the head on the leftmost 2, in state 1. An element -1 in the tag system corresponds to halting of the Turing machine. The different cases in the rules for the tag system are laid out on the left in the Turing machine. Each step of tag system evolution is implemented by having the head of the Turing machine scan as far to the left as it needs to get to the case of the tag system rule that applies—then copy the appropriate elements to the end of the sequence on the right. Note that although the Turing machine can emulate any number of colors in the tag system, it can only emulate directly rules that delete exactly 2 elements at each step. But since we know that at least with sufficiently many colors such tag systems are universal, it follows that the Turing machine is also universal.


From Stephen Wolfram: A New Kind of Science [citation]