Notes

Chapter 11: The Notion of Computation

Section 6: Emulating Cellular Automata with Other Systems


Tag systems [emulating cellular automata]

Given the rules for an elementary cellular automaton in the form used on page 867, the following will construct a tag system which emulates it:

CAToTS[rules_] := {2,{{s[x_], s[y_]} :> {d[x, y], d[x, y]}, {d[w_, x_], d[y_, z_]} :> {s[{w, x, y} /. rules], s[{x, y, z} /. rules]}, {s[x_], d[y_, z_]} :> {s[0], s[0], s[{0, y, z} /. rules]}, {d[x_, y_], s[z_]} :> {s[{x, y, 0} /. rules], s[0], s[0]}}}

The initial condition for the tag system that corresponds to a single black cell in the cellular automaton is {s[0],s[0],s[1],s[0],s[0]}. Given a list of all steps in the evolution of the tag system, Cases[list, {__s}] picks out successive steps in the cellular automaton evolution.

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