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, tapex, y} /. rule]



Image Source Notebooks:

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