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}]