Reconstructing cellular automata rules from observations at nonconsecutive times

Recent experiments have shown that a deep neural network can be trained to predict the action of $t$ steps of Conway's Game of Life automaton given millions of examples of this action on random initial states. However, training was never completely successful for $t>1$, and even when successful, a reconstruction of the elementary rule ($t=1$) from $t>1$ data is not within the scope of what the neural network can deliver. We describe an alternative network-like method, based on constraint projections, where this is possible. From a single data item this method perfectly reconstructs not just the automaton rule but also the states in the time steps it did not see. For a unique reconstruction, the size of the initial state need only be large enough that it and the $t-1$ states it evolves into contain all possible automaton input patterns. We demonstrate the method on 1D binary cellular automata that take inputs from $n$ adjacent cells. The unknown rules in our experiments are not restricted to simple rules derived from a few linear functions on the inputs (as in Game of Life), but include all $2^{2^n}$ possible rules on $n$ inputs. Our results extend to $n=6$, for which exhaustive rule-search is not feasible. By relaxing translational symmetry in space and also time, our method is attractive as a platform for the learning of binary data, since the discreteness of the variables does not pose the same challenge it does for gradient-based methods.

Figure 1

Node and edge variables highlighting (filled node, solid edges) those taking part in one CA rule constraint. In this example the CA has three inputs and each node variable has three upward projecting copies on edges (two of which are shown dashed).

Figure 2

The Rule 30 (left) and 110 (right) automata evolving with periodic boundary conditions, upward, from the same initial state.

Figure 3

RRR velocities for the three variable types ($v_y>v_x>v_z$) in a run of a Rule 30, $t=5$ reconstruction. The rule and unseen states were reconstructed in under $2.5\times {10}^4$ iterations.

Figure 4

Evolution of the eight rule-bits given by the concur estimates $z_B\left(0\right),...,z_B\left(7\right)$, for the same run shown in Fig. 3. RRR “time” runs left to right. The black rows on the right are the 1-bits of Rule 30.

Figure 5

Time evolution (upward) of Rule $X$ (4) from a random periodic state of length 200.

Figure 6

Complete evolution of the 64 rule-bits given by the concur estimates $z_B\left(0\right),...,z_B\left(63\right)$ in a reconstruction of Rule $X$ from $t=2$ data. Over the course of the search ($5.4\times {10}^4$ RRR iterations) many rule bits persist over long times. The fixed-point bits of Rule $X$ appear on the right.

Figure 7

A Boolean generative network for four-bit binary data and two-bit codes, showing the three variable types: $w$, $x$ (both on edges), and $y$ (gray nodes).

Figure 8

Wire state ($\varnothing$, $W$, $\overline{W}$) assignment in a fully connected $3\to 8$ BGN for an instance of correlated partitions. Data bits in the top row joined to the same code bit by wires with like (unlike) grayscale/color will be perfectly correlated (anticorrelated).

Figure 9

Data bits, in rows, for an $8\to 16$ instance of correlated partitions. Columns 3 and 5, for example, are identical because the bits at those positions are perfectly correlated.

Figure 10

A BGN that generates $2^3$ one-False vectors. The red (light-gray) edges are negating. For any setting of the nodes in the code layer a single Or in the data layer will be False.

Figure 11

A possible circuit in the second stage of a $3\to 8\to 8$ decoder for binary encoded data vectors. All wires (thick edges) are negating. The bottom (gray) nodes receive one-False vectors from a first stage of the kind shown in Fig. 10. For example, if the $F$ is at the leftmost input node, the decoder output is the data vector $FFFTFFFT$.

Figure 12

RRR evolution ($\sigma =0.6$, $\omega =0.5$, $\eta =0.9$, $\beta =0.5$), left to right, of the wire states (the component of the concur estimate $w_B$ that encodes negation) in a $3\to 8\to 8$ network learning to decode eight binary data vectors from a three-bit binary code. White corresponds to no wire, and the two colors (grayscales) give the wire-negation status as in earlier figures. The top 24 rows show the wire states in the first stage. Throughout most of the search the states considered in the two stages are close in character to the states in the solution, on the right.

Figure 13

Lower and upper bound $3\times 3$ masks for Life (top row) and $5\times 5$ Alien Life masks (bottom row). The corresponding “gates” take input on $9+8$ “wires” in the former, and $5+5$ wires in the latter.

Figure 14

Three time steps (upward) of Alien Life starting from a random state at the bottom.

Figure 15

Complete evolution of the two $5\times 5$ masks ($25+25$ rows) in an Alien Life rule reconstruction from $t=2$ data. The two five-wire masks of Alien Life appear on the right.