pith. sign in

arxiv: 1402.3766 · v1 · pith:XXJMTGU7new · submitted 2014-02-16 · 💻 cs.FL · nlin.CG

Turing degrees of limit sets of cellular automata

classification 💻 cs.FL nlin.CG
keywords cellularsetsautomatadegreesturingcomputablelimitpoint
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.