A Decidability Result for the Halting of Cellular Automata on the Pentagrid
Maurice Margenstern
LGIPM, Département Informatique et Applications
Université de Lorraine
3 rue Augustin Fresnel, BP 45112
57073 Metz, Cédex 03, France
Abstract
In this paper, we investigate the halting problem for deterministic cellular automata on the pentagrid. We prove that the problem is decidable when the cellular automaton starts its computation from a finite configuration and when it has two states, one of them being a quiescent state.
Keywords: tilings; hyperbolic plane; cellular automata; halting problem; decidability
