Reversible Cellular Automaton

A reversible cellular automaton is a CA in which every global configuration has exactly one predecessor, making the dynamics time-reversible. Reversible CAs are the discrete analogues of Hamiltonian systems: they conserve information, preserve phase-space volume, and satisfy a discrete Liouville theorem. Every irreversible CA can be embedded in a larger reversible one by retaining a history tape, a construction that mirrors the Loschmidt paradox in statistical mechanics. Reversible CAs connect to thermodynamics, information theory, and the foundations of physics, where the emergence of irreversibility from reversible microdynamics remains unresolved. They also matter for quantum computing and reversible computing, where information erasure carries thermodynamic cost.