Is it possible to reverse engineer cellular automata?

Question

Given a sequence of states of a given cellular automata, is it possible to construct the rules of the automata & hence predict the next state? To be clear, initially the rules are NOT known but the output sequence is.

Answer 1

This problem is somewhat similar to programming by example https://en.wikipedia.org/wiki/Programming_by_example

In this paradigm, a system is given a sequence of states (examples) and asked to synthesize a program that could generate that sequence. The system could be given many different examples and asked to synthesize a program that works with all provided examples.

To answer your question, yes it is possible. The simplest way to do this is to write a program that simply "remembers" all of the examples and outputs successive states when appropriate. If the synthesized program is asked to complete a step it has not seen in an example, then it simply outputs something arbitrary but deterministic.

This program may not give you what you want and would surely but large in size (larger than all of the provided examples combined); It can serve as an upper bound in program size. It is more interesting to minimize the size of this program and hope that the smaller program makes generalizations about the inputted examples and is thus more useful. If this minimal program makes a mistake somewhere (assuming you have distinct sets of examples for 'learning' and 'testing') then you can provide it with more examples that correct its mistakes.

Answer 2

As long appropriate initial constraints on the CA rule (and, in particular, on the neighborhood size) are provided, yes, this is possible.

In fact, the basic algorithm is quite simple. It relies on the fact that the transition rule for a CA with a finite number of states and a finite neighborhood size has a finite number of possible inputs, and can thus be generically represented as a rule table mapping each possible input neighborhood to an output cell state:

1. Start with an initial rule table mapping each neighborhood to an extra "unknown" state.

2. For each cell in the input sequence (except for the final step), look up the output cell state for its neighborhood in the rule table. If it's currently unknown, set it to the actual observed state of the cell in the next generation. Otherwise, if it doesn't match the observed next-generation state, abort with an error.

3. Once all cells have been successfully processed, output the resulting rule table.

Note that the resulting rule table may still have some unknown output cell states if the corresponding neighborhoods never occur in the input sequence. Replacing such unknown cell states with any valid cell state will produce a CA rule compatible with the input sequence.

It is not, of course, guaranteed that each of these possible rules will produce the same next state. However, if the input is sufficiently representative of typical neighborhoods that occur during the evolution of the CA then this is quite likely to be the case.

---

Also note that if the given input sequence consists only of slices of a larger lattice, rather than the entire state of a finite lattice with known boundary conditions, then the neighborhoods of cells near the spatial edges of the input sequence may not be fully defined.

Such cells cannot be processed as described in step 2 above. We can, of course, simply skip such cells in step 2 and just hope that the remaining cell transitions in the input are sufficient to define the CA rule, and then later verify that the resulting rule is also compatible with the skipped edge cells.

More generally, to ensure that the rule(s) we find are exactly those compatible with the given input even at the edges, we'd need to find some self-consistent assignment of cell states not only to the neighborhoods in the rule table but also to cells outside the edges of the input slices. In general, this can be formulated as a boolean satisfiability (SAT) problem and passed to a general-purpose SAT solver. In fact, there already exist programs that can do exactly that, at least for certain classes of CA rules, such as Logic Life Search (LLS), which can perform exactly this kind of search for a class of CA rules that includes e.g. Conway's Game of Life.

(In fact, LLS can do a lot more than that — it can also e.g. fill in gaps in the input sequence or even search ex nihilo for rules and/or sequences that satisfy certain boundary conditions, such as ones with the initial input state reappearing after $n$ generations, but shifted a certain number of cells — i.e. for spaceships.)