Notes

Chapter 5: Two Dimensions and Beyond

Section 3: Turing Machines


Implementation [of 2D Turing machines]

With rules represented as a list of elements of the form {s, a} -> {sp, ap, {dx, dy}} (s is the state of the head and a the color of the cell under the head) each step in the evolution of a 2D Turing machine is given by

TM2DStep[rule_, {s_, tape_, r:{x_, y_}}] := Apply[{#1, ReplacePart[tape, #2, {r}], r + #3}&, {s, tape[[x, y]]} /. rule]


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