The Complexity of Reversible Cellular Automata on Infinite Configurations

Jesse Clark
Carnegie Mellon University

A key point of NKS is the computational universality of certain cellular automata. Sutner has constructed reversible one-dimensional cellular automata of intermediate (less than universal) Turing degree by simulation of  intermediate-degree Turing machines.

Sutner’s construction uses tracks that left-shift and right-shift their contents at every step, allowing for the propagation of signal bits  that simplify the Reachability problem. He has shown that the behavior of the signal system is trivial on finite configurations.

We examine the signal system and show that its behavior is trivial even on infinite periodic configurations. It is impossible to construct domain walls or produce behavior more complex than parenthesis-balancing, so it cannot increase the degree of an automaton beyond the degree of the Turing machine being simulated.

The signal system is not strictly reversible: there are “Garden of Eden” states which can have no ancestor. However, this does not introduce ambiguity to the simulation of a legitimate Turing machine. We analyze the consequences of semi-reversibility for the Confluence and Reachability problems.

Created by Mathematica  (April 20, 2004)