@inproceedings{c31ca08866d54ce2bc55c1e22f79875a,
title = "Turing degrees of limit sets of cellular automata",
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 limit sets of cellular automata: they are the same as the sets of Turing degrees of effectively closed sets containing a computable point.",
author = "Alex Borello and Julien Cervelle and Pascal Vanier",
year = "2014",
month = jan,
day = "1",
doi = "10.1007/978-3-662-43951-7\_7",
language = "English",
isbn = "9783662439500",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
number = "PART 2",
pages = "74--85",
booktitle = "Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings",
edition = "PART 2",
note = "41st International Colloquium on Automata, Languages, and Programming, ICALP 2014 ; Conference date: 08-07-2014 Through 11-07-2014",
}