On the Circuit Depth of Structurally Reversible Cellular Automata

Article type: Research Article

Authors: Kari, Jarkko

Affiliations: Department of Computer Science, 14 MacLean Hall, University of Iowa, Iowa City, IA 52242, USA [email protected]

Note: [] Address for correspondence: Department of Computer Science, 14 MacLean Hall, University of Iowa, Iowa City, IA 52242, USA

Abstract: We study the family of structurally reversible cellular automata that use the (generalized) Margolus neighborhoods. We show that every reversible cellular automaton (RCA) can be embedded into the standard two layer Margolus neighborhood defined by two overlapping square partitions of the cellular space and two one-to-one local rules. The embedding allows step-by-step simulations. Then we investigate how many layers of one-to-one local rules are required in exact representations of RCA. We show how in the d-dimensional cellular space any consecutive d + 2 layers can be combined into d + 1 layers. This proves that no more than d + 1 layers are necessary. We demonstrate that in the two-dimensional case d = 2 the number d + 1 is optimal by providing an example of an RCA with three layers of local rules that cannot be expressed in two layers.

Keywords: Cellular automata, reversible computation

DOI: 10.3233/FI-1999-381208

Journal: Fundamenta Informaticae, vol. 38, no. 1-2, pp. 93-107, 1999