But if there are an infinite number of elements that can be specified in the initial condition—as in a cellular automaton—then a table for an oracle could also be given in the initial conditions.

Spacetime patches [in cellular automata] One can imagine defining entropies and dimensions associated with regions of any shape in the spacetime history of a cellular automaton. … But in fact, having just specified a block of length x + 2 r t in the initial conditions, the cellular automaton rule then uniquely determines the color of every cell in the patch, allowing a total of at most s[t, x] = k x + 2 r t configurations. … Just as for most other entropies, when a cellular automaton shows complicated behavior it tends to be difficult to find much more than upper bounds for h tx .

Undecidability in cellular automata For 1D cellular automata, almost all questions about ultimate limiting behavior are undecidable, even ones that ask about average properties such as density and entropy. … In 2D cellular automata, however, even questions about a single step are often undecidable. Examples include whether any configurations are invariant under the cellular automaton evolution (see page 942 ), and, as established by Jarkko Kari in the late 1980s, whether the evolution is reversible, or can generate every possible configuration (see page 959 ).

Comparison of [periods for cellular automaton] rules Rules 45, 30 and 60, together with their conjugates and reflections, yield the longest repetition periods of all elementary rules (see page 1087 ).

Note (f) for More Cellular Automata…Compositions of cellular automata One way to construct more complicated rules is from compositions of simpler rules. One can, for example, consider each step applying first one elementary cellular automaton rule, then another.

Note (c) for Cellular Automata…Cellular automaton art 2D cellular automata can be used to make a wide range of designs for rugs, wallpaper, and similar objects.

Cellular Automata…cellular automata. … But it is nevertheless possible to find two-dimensional cellular automata that yield less regular shapes. … And so it seems that there can be great complexity not only in the detailed arrangement of black and white cells in a two-dimensional cellular automaton pattern, but also in the overall shape of the pattern.

Note (b) for More Cellular Automata…Implementation of general cellular automata With k colors and r neighbors on each side, a single step in the evolution of a general cellular automaton is given by CAStep[CARule[rule_List, k_, r_], a_List] := rule 〚 -1 - ListConvolve[k^Range[0, 2r], a, r + 1] 〛 where rule is obtained from a rule number num by IntegerDigits[num, k, k 2r + 1 ] .

For much as on page 943 , one can imagine setting up a 1D cellular automaton with the property that, say, the absence of a particular color of cell throughout the 2D pattern formed by its evolution signifies satisfaction of the constraints. But even starting from a fixed line of cells, the question of whether a given color will ever occur in the evolution of a 1D cellular automaton is in general undecidable, as discussed in the main text.

Yet looking at these patterns one notices a remarkable similarity to patterns that we have seen many times before in this book—generated by simple one-dimensional cellular automata. … In each close-up the pattern grows from top to bottom, just like in a one-dimensional cellular automaton.