Universal Computing in Reversible and Number-Conserving Two-Dimensional Cellular Spaces

A number-conserving reversible cellular automaton (NC-RCA) is a computing model that reflects both reversibility and mass or energy conservation law in physics. We show that, despite strict constraints of reversibility and number-conservation, there exist simple two-dimensional NC-RCAs that are capable of universal computation. These automata are classified into two types. Automaton of the first type implements a Fredkin gate in its space-time dynamic. That is a Fredkin gate, as a universal logical element, is embedded in its cellular space. Automaton of the second type, incorporate a novel logical element, called a “rotary element” in its lattice dynamic. NC-RCAs of the second type simulate any reversible two-counter machine in their space-time configuration. In both types of cellular automata the computation is realized via appropriate control of “moving particles” in the cellular space.