 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}]
|
Send a Message
