Towards the Frontier between Decidability and Undecidability for Hyperbolic Cellular Automata

摘要

In this paper, we look at two ways to implement one dimensional cellular automata into hyperbolic cellular automata in three contexts: the pentagrid, the heptagrid and the dodecagrid, these tilings being classically denoted by {5,4}, {7,3} and {5,3,4} respectively. As an application, this may give a hint for the boundary between decidable and undecidable problems for hyperbolic cellular automata.