Computability of Countable Subshifts in One Dimension

作者：Cenzer Douglas^*; Dashti Ali; Toska Ferit; Wyman Sebastian

来源：Theory of Computing Systems, 2012, 51(3): 352-371.

DOI：10.1007/s00224-011-9358-z

• Computability
• Symbolic dynamics
• Pi(0)(1) classes

We investigate the computability of countable subshifts in one dimension, and their members. Subshifts of Cantor-Bendixson rank two contain only eventually periodic elements. Any rank two subshift in 2(Z) is decidable. Subshifts of rank three may contain members of arbitrary Turing degree. In contrast, effectively closed (Pi(0)(1)) subshifts of rank three contain only computable elements, but Pi(0)(1) subshifts of rank four may contain members of arbitrary Delta(0)(2) degree. There is no subshift of rank omega + 1.

• 出版日期2012-10