Skip to Main content Skip to Navigation
Conference papers

Revisiting the Rice Theorem of Cellular Automata

Pierre Guillon 1, * Gaétan Richard 2 
* Corresponding author
2 Equipe AMACC - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image et Instrumentation de Caen
Abstract : A cellular automaton is a parallel synchronous computing model, which consists in a juxtaposition of finite automata whose state evolves according to that of their neighbors. It induces a dynamical system on the set of configurations, i.e. the infinite sequences of cell states. The limit set of the cellular automaton is the set of configurations which can be reached arbitrarily late in the evolution. In this paper, we prove that all properties of limit sets of cellular automata with binary-state cells are undecidable, except surjectivity. This is a refinement of the classical "Rice Theorem" that Kari proved on cellular automata with arbitrary state sets.
Document type :
Conference papers
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Thursday, February 11, 2010 - 9:35:56 AM
Last modification on : Saturday, June 25, 2022 - 9:46:24 AM
Long-term archiving on: : Friday, June 18, 2010 - 8:08:05 PM


Files produced by the author(s)


  • HAL Id : inria-00455736, version 1


Pierre Guillon, Gaétan Richard. Revisiting the Rice Theorem of Cellular Automata. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Inria Nancy Grand Est & Loria, Mar 2010, Nancy, France. pp.441-452. ⟨inria-00455736⟩



Record views


Files downloads