Chapter 3: The World of Simple Programs

Section 3: Mobile Automata

Implementation [of mobile automata]

The state of a mobile automaton at a particular step can conveniently be represented by a pair {list, n}, where list gives the values of the cells, and n specifies the position of the active cell (the value of the active cell is thus list[[n]]). Then, for example, the rule for the mobile automaton shown on page 71 can be given as

{{1,1,1}->{0,1}, {1,1,0}->{0,1}, {1,0,1}->{1,-1}, {1,0,0}->{0,-1}, {0,1,1}->{0,-1}, {0,1,0}->{0,1}, {0,0,1}->{1,1}, {0,0,0}->{1,-1}}

where the left-hand side in each case gives the value of the active cell and its left and right neighbors, while the right-hand side consists of a pair containing the new value of the active cell and the displacement of its position. (In analogy with cellular automata, this rule can be labelled {35,57} where the first number refers to colors, and the second displacements.) With a rule given in this form, each step in the evolution of the mobile automaton corresponds to the function

MAStep[rule_, {list_List, n_Integer}] /; (1 < n < Length[list]) := Apply[{ReplacePart[list, #1, n], n + #2}&, Replace[Take[list, {n-1, n+1}], rule]]

The complete evolution for many steps can then be obtained with

MAEvolveList[rule_, init_List, t_Integer] := NestList[MAStep[rule, #]&, init, t]

(The program will run more efficiently if Dispatch is applied to the rule before giving it as input.)

For the mobile automaton on page 73, the rule can be given as

{{1,1,1}->{{0,0,0},-1}, {1,1,0}->{{1,0,1},-1}, {1,0,1}->{{1,1,1},1}, {1,0,0}->{{1,0,0},1}, {0,1,1}->{{0,0,0},1}, {0,1,0}->{{0,1,1},-1}, {0,0,1}->{{1,0,1},1}, {0,0,0}->{{1,1,1},1}}

and MAStep must be rewritten as

MAStep[rule_, {list_List, n_Integer}] /; (1 < n < Length[list]) := Apply[{Join[Take[list, {1, n-2}], #1, Take[list, {n+2, -1}]], n + #2}&, Replace[Take[list, {n-1, n+1}], rule]]

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