A family of weakly universal cellular automata in the hyperbolic plane with two states

Abstract

In this paper, we construct a family of weakly universal rotation invariant cellular automaton for all grids $\{p,3\}$ of the hyperbolic plane for $p\ge 13$. The scheme is general for $p\ge 17$ and for $13\le p<17$, we give such a cellular automaton for $p=13$, which is enough. Also, an important property of this family is that the set of cells of the cellular automaton which are subject to changes is actually a planar set. The problem for $p<13$ for a truly planar construction is still open. The best result, for $p=7$, is four states and was obtained by the same author.

83 pages, 38 figures, 53 tables. arXiv admin note: text overlap with arXiv:0903.2108

References in corpus (1)

• About the domino problem in the hyperbolic plane, a new solution: complement

Cited by in corpus (3)

• A weakly universal cellular automaton with 2 states on the tiling {11,3}
• A weakly universal cellular automaton on the tessellation $\{8,3\}$
• A weakly universal cellular automaton in the heptagrid