Turing Degrees of Limit Sets of Cellular Automata

DOI10.1007/978-3-662-43951-7_7zbMATH Open1409.68181arXiv1402.3766OpenAlexW147092118MaRDI QIDQ5167828FDOQ5167828

Pascal Vanier, Julien Cervelle, Alex Borello

Publication date: 1 July 2014

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

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.

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

Mathematics Subject Classification ID

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

Cited In (4)

• Complexity of generic limit sets of cellular automata
• Cellular automata and intermediate degrees.
• Title not available (Why is that?)
• Inferring the Limit Behavior of Some Elementary Cellular Automata

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)