Complex Systems

A Weakly Universal Cellular Automaton in the Heptagrid of the Hyperbolic Plane Download PDF

Maurice Margenstern
LGIPM, Department of Computer Science and Applications
Université de Lorraine
3 rue Augustin Fresnel, BP 45112, 57073 Metz, Cédex 03, France


In this paper, we construct a weakly universal cellular automaton (CA) in the heptagrid, the tessellation {7, 3} that takes place in the hyperbolic plane. The CA is not rotation invariant but is truly planar. This result, under these conditions, cannot be improved for the tessellations {p, 3} of the hyperbolic plane.

Keywords: cellular automata; tessellations; hyperbolic plane; weak universality; railway model