Turing degrees of limit sets of cellular automata

DOI10.1007/978-3-662-43951-7_7MaRDI QIDQ5167828zbMATH OpenOpenAlexFDO

Authors Alex Borello, Julien Cervelle, Pascal Vanier

Publication date 1 July 2014

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.3766

Mathematics Subject Classification ID

Other Turing degree structures (03D28) Cellular automata (computational aspects) (68Q80)

Abstract: 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.

Recommendations

• scientific article; zbMATH DE number 919608
• Revisiting the Rice theorem of cellular automata
• On the undecidability of the limit behavior of cellular automata
• Undecidable properties of limit set dynamics of cellular automata
• On the Limit Sets of Cellular Automata

Cited in

(4)

• Cellular automata and intermediate degrees.
• Complexity of generic limit sets of cellular automata
• Inferring the Limit Behavior of Some Elementary Cellular Automata
• scientific article; zbMATH DE number 919608 (Why is no real title available?)

This page was built for publication: Turing degrees of limit sets of cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5167828)