# Reconstructing cellular automata rules from observations at nonconsecutive times

arXiv: https://arxiv.org/abs/2012.02179 · HTML: https://mlsanity.com/paper/2012.02179/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Dec 2020.

## Built on by (most cited first, 5 of 5)

- [Learning Elementary Cellular Automata with Transformers](https://mlsanity.com/paper/2412.01417/) (2024)
- [Beyond Memorization: Extending Reasoning Depth with Recurrence, Memory and Test-Time Compute Scaling](https://mlsanity.com/paper/2508.16745/) (2025)
- [Avoiding Traps in Nonconvex Problems](https://mlsanity.com/paper/2106.05206/) (2021)
- [Learning grammar with a divide-and-concur neural network](https://mlsanity.com/paper/2201.07341/) (2022)
- [Transformers Can Learn Rules They've Never Seen: Proof of Computation Beyond Interpolation](https://mlsanity.com/paper/2603.17019/) (2026)

## Abstract (arXiv)

Recent experiments by Springer and Kenyon 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 22n 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.