Reversible space–time simulation of cellular automata

✍ Scribed by Jérôme O. Durand-Lose

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 276 KB
• Volume: 246
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(99)00075-4

✦ Synopsis

The goal of this paper is to design a reversible d-dimensional cellular automaton which is capable of simulating the behavior of any given d-dimensional cellular automaton over any given conÿguration (even inÿnite) with respect to a well suited notion of simulation we introduce. We generalize a problem which was originally addressed in a paper by To oli 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 deÿned by Morita et al. in 1989.