2014/02/16 by Alex Borello, Borello, Alex, Julien Cervelle +3
Computer Science · Mathematics · #Cellular Automata and Applications #Cellular Automata and Lattice Gases (nlin.CG) #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #FOS: Physical sciences #Formal Languages and Automata Theory (cs.FL) #Mathematical Dynamics and Fractals
paper · doi:10.48550/arxiv.1402.3766
openalex publication_date 2014/02/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Cellular automata are discrete dynamical systems and a model of computation. The limit set of a cellular automaton consists of the configurations having an infinite sequence of preimages. It is well known that these always contain a computable point and that any non-trivial property on them is undecidable. We go one step further in this article by giving a full characterization of the sets of Turing degrees of cellular automata: they are the same as the sets of Turing degrees of effectively closed sets containing a computable point.