Rule 22 [with simple initial conditions] Randomness is obtained with initial conditions consisting of two black squares 4 m positions apart for any m ≥ 2 .

Satisfiability [emulating Turing machines] Given variables  [t, s] ,  [t, x, a] ,  [t, n] representing whether at step t a non-deterministic Turing machine is in state s , the tape square at position x has color a , and the head is at position n , the following CNF expression represents the assertion that a Turing machine with stot states and ktot possible colors follows the specified rules and halts after at most t steps: NDTMToCNF[rules_, {s_, a_, n_}, t_] := {Table[Apply[Or, Table[  [i, j], {j, stot}]], {i, t - 1}], Table[!

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.

The second-to-last case always has a black element at every third position, so exhibits a peak at the corresponding repetition frequency.

Sequence (e) is generated by a linear feedback shift register (essentially an additive cellular automaton) with tap positions {2, 11} .

Because of additivity it turns out that one can deduce whether or not some cell a certain number of steps down a given column is black just by seeing whether there are an odd or even number of black cells in certain specific positions in the row at the top.

So in a simple case if one has an array of black and white squares, what one would typically look for is a formula that takes the numbers which specify the position of a particular square and from these tells one whether the square is black or white.

And thus, for example, an early triumph of theoretical science was the derivation of a formula for the position of a single idealized planet orbiting a star.

Picture (b) has a black square wherever digits at more than half the possible positions differ between the x and y coordinates.

[Examples of] reducible systems The color of a cell at step t and position x can be found by starting with initial condition Flatten[With[{w = Max[Ceiling[Log[2, {t, x}]]]}, {2 Reverse[IntegerDigits[t, 2, w]] + 1, 5, 2 IntegerDigits[x, 2, w] + 2}]] then for rule 188 running the cellular automaton with rule {{a : (1 | 3), 1 | 3, _}  a, {_, 2 | 4, a : (2 | 4)}  a, {3, 5 | 10, 2}  6, {1, 5 | 7, 4}  0, {3, 5, 4}  7, {1, 6, 2}  10, {1, 6 | 11, 4}  8, {3, 6 | 8 | 10 | 11, 4}  9, {3, 7 | 9, 2}  11, {1, 8 | 11, 2}  9, {3, 11, 2}  8, {1, 9 | 10, 4}  11, {_, a_ /; a > 4, _}  a, {_, _, _}  0} and for rule 60 running the cellular automaton with rule {{a : (1 | 3), 1 | 3, _}  a, {_, 2 | 4, a : (2 | 4)}  a, {1, 5, 4}  0, {_, 5, _}  5, {_, _, _}  0}