zbMATH — the first resource for mathematics

Computability of countable subshifts. (English) Zbl 1285.03054
Ferreira, Fernando (ed.) et al., Programs, proofs, processes. 6th conference on computability in Europe, CiE 2010, Ponta Delgada, Azores, Portugal, June 30–July 4, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-13961-1/pbk). Lecture Notes in Computer Science 6158, 88-97 (2010).
Summary: The computability of countable subshifts and their members is examined. Results include the following. Subshifts of Cantor-Bendixson rank one contain only eventually periodic elements. Any rank one subshift, in which every limit point is periodic, is decidable. Subshifts of rank two may contain members of arbitrary Turing degree. In contrast, effectively closed ($$\Pi^0_1$$) subshifts of rank two contain only computable elements, but $$\Pi^0_1$$ subshifts of rank three may contain members of arbitrary c.e. degree. There is no subshift of rank $$\omega$$.
For the entire collection see [Zbl 1192.68009].

MSC:
 03D30 Other degrees and reducibilities in computability and recursion theory 03D78 Computation over the reals, computable analysis 37B10 Symbolic dynamics
Full Text: