Notes

Chapter 3: The World of Simple Programs

Section 4: Turing Machines


Implementation [of Turing machines]

The state of a Turing machine at a particular step can be represented by the triple {s, list, n}, where s gives the state of the head, list gives the values of the cells, and n specifies the position of the head (the cell under the head thus has value list[[n]]). Then, for example, the rule for the Turing machine shown on page 78 can be given as

{{1, 0} -> {3, 1, -1}, {1, 1} -> {2, 0, 1}, {2, 0} -> {1, 1, 1}, {2, 1} -> {3, 1, 1}, {3, 0} -> {2, 1, 1}, {3, 1} -> {1, 0, -1}}

where the left-hand side in each case gives the state of the head and the value of the cell under the head, and the right-hand side consists of a triple giving the new state of the head, the new value of the cell under the head and the displacement of the head.

With a rule given in this form, a single step in the evolution of the Turing machine can be implemented with the function

TMStep[rule_List, {s_, a_List, n_}] /; (1<=n<=Length[a]) := Apply[ {#1, ReplacePart[a, #2, n], n + #3}&, Replace[ {s, a[[n]]}, rule ] ]

The evolution for many steps can then be obtained using

TMEvolveList[rule_, init_List, t_Integer] := NestList[TMStep[rule, #]&, init, t]

An alternative approach is to represent the complete state of the Turing machine by MapAt[{s, #}&, list, n], and then to use

TMStep[rule_, c_] := Replace[c, {a___, x_, h_List, y_, b___} :> Apply[{{a, x, #2, {#1, y}, b}, {a, {#1, x}, #2, y, b}}[[#3]] &, h /. rule]]

The result of t steps of evolution from a blank tape can also be obtained from (see also page 1143)

s = 1; a[_] = 0; n = 0; Do[{s, a[n], d} = {s, a[n]} /. rule; n += d, {t}]

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