Encodings [of cellular automaton rules]

Generalizing the setup in the main text one can say that a cellular automaton i can emulate j if there is some encoding function ϕ that encodes the initial conditions a_j for j as initial conditions for i, and which has an inverse that decodes the outcome for i to give the outcome for j. With evolution functions f_i and f_j the requirement for the emulation to work is

f_j[a_j]  InverseFunction[ϕ][f_i[ϕ[a_j]]]

In the main text the encoding function is taken to have the form Flatten[a /. rules]—where rules are say {1  {1, 1}, 0  {0, 0}}—with the result that the decoding function for emulations that work is Partition[ã, b] /. Map[Reverse, rules].

An immediate generalization is to allow rules to have a form like {1  {1, 1}, 1  {1, 0}, 0  {0, 0}} in which several blocks are in effect allowed to serve as possible encodings for a single cell value. Another generalization is to allow blocks at a variety of angles (see above). In most cases, however, introducing these kinds of slightly more complicated encodings does not fundamentally seem to expand the set of rules that a given rule can emulate. But often it does allow the emulations to work with smaller blocks. And so, for example, with the setup shown in the main text, rule 54 can emulate rule 0 only with blocks of length b = 6. But if either multiple blocks or δ = 1 are allowed, b can be reduced to 4, with rules being {1  {1, 1, 1, 1}, 0  {0, 0, 0, 0}, 0  {0, 1, 1, 1}} and {0  {0, 1, 0, 0}, 1  {0, 0, 1, 0}} in the two cases.

Various questions about encoding functions ϕ have been studied over the past several decades in coding theory. The block-based encodings discussed so far here correspond to block codes. Convolutional codes (related to sequential cellular automata) are the other major class of codes studied in coding theory, but in their usual form these do not seem especially useful for our present purposes.

In the most general case the encoding function can involve an arbitrary terminating computation (see page 1126). But types of encoding functions that are at least somewhat powerful yet can realistically be sampled systematically may perhaps include those based on neighbor-dependent substitution systems, and on formal languages (finite automata and generalizations).