DMTCS Proceedings, Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001

Font Size:  Small  Medium  Large

Representing Reversible Cellular Automata with Reversible Block Cellular Automata

Jérôme Durand-Lose


Cellular automata are mappings over infinite lattices such that each cell is updated according to the states around it and a unique local function. Block permutations are mappings that generalize a given permutation of blocks (finite arrays of fixed size) to a given partition of the lattice in blocks. We prove that any d-dimensional reversible cellular automaton can be exp ressed as the composition of d+1 block permutations. We built a simulation in linear time of reversible cellular automata by reversible block cellular automata (also known as partitioning CA and CA with the Margolus neighborhood) which is valid for both finite and infinite configurations. This proves a 1990 conjecture by Toffoli and Margolus Physica D 45 improved by Kari in 1996 Mathematical System Theory 29).

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional