Reversible Cellular Automaton Able to Simulate

Reversible Cellular Automaton Able to Simulate Any Other Reversible One Using Partitioning Automata Jérôme Olivier Durand-Lose ? Departamento de Ingeniería Matemática, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Santiago, Chile. e-mail: LATIN '95, LNCS 911, pp. 230244 Abstract. Partitioning automata (PA) are dened. They are equivalent to cellular automata (CA). Reversible sub-classes are also equivalent. A simple, reversible and universal partitioning automaton is described. Finally, it is shown that there are reversible PA and CA that are able to simulate any reversible PA or CA on any conguration. 1 Introduction The main interest of reversibility in computation is backtracking a phenomenon to its source and in relation with physics, isoentropic phenomena modelization and saving energy, and had have various interests in relation to physics as ex- plained by Tooli and Margolus in [15]. It is well known that, given any d- dimensional cellular automata (CA), it can be simulated by one (d+1)-dimensio- nal CA which is reversible [12]. It is still an open problem if it can be simulated by a reversible CA of the same dimension. For example, Morita showed in [7] that this is true in dimension one but only over nite congurations.

• both nite


• simulate any reversible


• can simulate


• called nodes


• partition


• reversible pa


• transition function