Reversible space-time simulation of cellular automata
The goal of this paper is to design a reversible d-dimensional cellular automaton which is capable of simulating the behavior of any given cl-dimensional cellular automaton over any given configuration (even infinite) with respect to a well suited notion of simulation we introduce, We generalize a problem which was originally addressed in a paper by Toffoli in 1977. He asked whether a d-dimensional reversible cellular automaton could simulate d-dimensional cellular automata, In the same paper he proved that there exists a (d+1)-dimensional reversible cellular automaton which can simulate a given d-dimensional cellular automaton. To prove our result, we use as an intermediate model partition cellular automata defined by Morita ct al. in 1989, (C) 2000 Published by Elsevier Science B.V. All rights reserved.
space-time simulation (partitioned) cellular automata intrinsic universality and reversibility