Abstract
Reversible Cellular Automata (RCA) are shift-invariant transformations characterized by dynamics composed only of disjoint cycles. They have many applications in the simulation of physical systems, cryptography, and reversible computing. In this work, we formulate the search of a specific class of RCA – namely, those whose local update rules are defined by conserved landscapes – as an optimization problem to be tackled with Genetic Algorithms (GA) and Genetic Programming (GP). In particular, our experimental investigation revolves around three different research questions, which we address through a single-objective, a multi-objective, and a lexicographic approach. In the single-objective approach, we observe that GP can already find an optimal solution in the initial population. This indicates that evolutionary algorithms are not needed when evolving only the reversibility of such CA, and a more efficient method is to generate at random syntactic trees that define the local update rule. On the other hand, GA and GP proved to be quite effective in the multi-objective and lexicographic approach to (1) discover a trade-off between the reversibility and the Hamming weight of conserved landscape rules, and (2) observe that conserved landscape CA cannot be used in symmetric cryptography because their Hamming weight (and thus their nonlinearity) is too low.
Introduction: The Challenge of Reversibility
Cellular Automata (CA) are discrete dynamical systems used to model complex phenomena ranging from biological growth to physical particle interactions. A CA consists of a grid of cells, each in a specific state, which evolves over time according to a local update rule applied to every cell simultaneously.
Reversible CA (RCA) are a subset of these systems where the global dynamics are bijective, meaning the system can run both forward and backward in time without losing information. This property makes RCA essential for energy-efficient "green" computing and cryptographic applications. However, identifying rules that guarantee reversibility is a "needle in a haystack" problem. As the neighborhood size (diameter) of the CA increases, the search space grows exponentially—reaching $2^{2^{14}}$ possible rules for a diameter of 15—making exhaustive search impossible.
Methodology: Evolutionary Heuristics
This study explores the use of evolutionary algorithms to discover new reversible rules, specifically focusing on Marker CA. In this class, a cell flips its state only if its neighbors match a specific pattern, known as a "landscape." If these landscapes are "conserved" (never destroyed by the update), the CA is guaranteed to be reversible.
The researchers compared two primary evolutionary representations:
- Genetic Algorithms (GA): The local update rule is represented as a bitstring (a truth table).
- Genetic Programming (GP): The rule is represented as a symbolic tree of Boolean operations (AND, OR, NOT, etc.).
The optimization was conducted across three scenarios: a single-objective search for reversibility, a lexicographic approach prioritizing reversibility then Hamming weight, and a multi-objective approach (NSGA-II) to find the "Pareto front" of trade-offs between these two goals.
Key Insights
The Efficiency of Genetic Programming
A surprising result of the study was that GP consistently found optimal reversible rules in its initial population (Generation 0). This suggests that for this specific mathematical domain, the tree-based representation of GP is naturally biased toward "simple" functions. In the context of conserved landscape rules, these simple functions are highly likely to be reversible. Consequently, for single-objective reversibility, a simple random search of Boolean trees is more efficient than a full evolutionary process.
The "Balanced" Curse of Genetic Algorithms
In contrast, GA struggled significantly as the diameter increased. Randomly generated bitstrings tend to be "balanced" (having an equal number of 0s and 1s). The authors demonstrated that balanced functions are mathematically the furthest from being reversible within the conserved landscape class. Thus, GA begins its search in the least favorable region of the search space.
Cryptographic Limitations
In cryptography, high nonlinearity is required to resist attacks, and Hamming weight serves as a proxy for this property. The multi-objective results revealed a stark trade-off: as a conserved landscape rule becomes more reversible, its Hamming weight—and therefore its cryptographic utility—decreases. This indicates that while these rules are easy to evolve, they are likely too simple for high-end symmetric cryptography.
Conclusion and Future Directions
While evolutionary algorithms, particularly GP, are highly effective at finding reversible rules, the "conserved landscape" constraint limits the resulting RCA to simple dynamics (cycles of length 2). Future research will focus on relaxing this constraint, allowing landscapes to overlap. This could enable the discovery of a broader class of RCA with the high nonlinearity required for robust cryptographic ciphers.
Summary updated