But unlike in a cellular automaton even given a complete x (the analog of a complete cellular automaton state) it is difficult to invert the mapping and solve for the x on the previous step.

Cellular automaton axioms The first 4 axioms are general to one-dimensional cellular automata.

Generalized additive [cellular automaton] rules Additive cellular automata of the kind discussed on page 952 can be generalized by allowing the new value of each cell to be obtained from combinations of cells on s previous steps.

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.)

General associative [cellular automaton] rules With a cellular automaton rule in which the new color of a cell is given by f[a 1 , a 2 ] (compare page 886 ) it turns out that the pattern generated by evolution from a single non-white cell is always nested if the function f has the property of being associative or Flat . … The result can also be generalized to cellular automata with basic rules involving more than two elements—since if f is Flat , f[a 1 , a 2 , a 3 ] is always just f[f[a 1 , a 2 ], a 3 ] .

In a system like a cellular automaton that is based on explicit rules, it is always straightforward to take the rule and apply it to see Examples of patterns produced by systems in which not only must the arrangement of colors in each neighborhood match one of a fixed set of templates, but also a certain template from this set must occur at least once in the pattern.

With different initial conditions this cellular automaton from page 339 can evolve either to uniform white or uniform black.

The interior of the pattern that emerges is like an inverted version of the rule 60 additive cellular automaton; the boundary, however, is more complicated.

Or does the notion of computation somehow apply only to systems with abstract elements like, say, the black and white cells in a cellular automaton?

Most schemes like this can ultimately be thought of as picking out templates or applying simple cellular automaton rules.