Computation and construction universality of reversible cellular automata

摘要

An arbitrary d-dimensional cellular automaton can be constructively embedded in areversible one having d+1 dimensions. In particular, there exist computation- and construction-universal reversible cellular automata. Thus, we explicitly show a way of implementing nontrivial irreversible processes in a reversible medium. Finally, we derive new results for the bounding problem for configurations, both in general and for reversible cellular automata.