A Strongly Universal Cellular Automaton in the Dodecagrid with Five States
Maurice Margenstern
In this paper, we prove that there is a strongly universal cellular automaton in the dodecagrid, the tessellation {5, 3, 4} of the hyperbolic 3D space, with five states which is rotation invariant. This improves a previous paper of the author where the automaton required ten states. At the occasion of that result, we also give a sufficient condition for a decidable halting problem with respect to the computation of a cellular automaton in the dodecagrid starting from a finite configuration.
Keywords: Cellular automata, 3D hyperbolic space, strong universality