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 onedimensional cellular automata of intermediate (less than universal) Turing degree by simulation of intermediatedegree Turing machines.
Sutner’s construction uses tracks that leftshift and rightshift 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 parenthesisbalancing, 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 semireversibility for the Confluence and Reachability problems.
Created by
Mathematica
(April 20, 2004)
