JCA HomeIssue Contents

A Uniform and Intrinsic Proof that there are Universal Cellular Automata in Hyperbolic Spaces
Maurice Margenstern

Many proofs about universality are performed by reduction to a well known universal process. Direct proofs of a simulation of any cellular automaton working on finite configurations by some other one satisfying the same constraint are known for the line and for planar cellular automata in the Euclidean case. In this paper, we give the construction of such a direct simulation for cellular automata in the hyperbolic plane. The construction is valid for infinitely many grids of the hyperbolic plane and also for the dodecahedral rectangular grid of the hyperbolic 3D space. It can be extended to the general context of cellular automata defined on a combinatoric tiling.

Full Text (IP)