×

zbMATH — the first resource for mathematics

Computability of countable subshifts in one dimension. (English) Zbl 1285.03055
Summary: 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^{\mathbb 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\).

MSC:
03D30 Other degrees and reducibilities in computability and recursion theory
03D78 Computation over the reals, computable analysis
37B10 Symbolic dynamics
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bournez, O., Cosnard, M.: On the computational power of dynamical systems and hybrid systems. Theor. Comput. Sci. 168, 417–459 (1996) · Zbl 0874.68303 · doi:10.1016/S0304-3975(96)00086-2
[2] Braverman, M., Yampolsky, M.: Non-computable Julia sets. J. Am. Math. Soc. 19, 551–578 (2006) · Zbl 1099.37042 · doi:10.1090/S0894-0347-05-00516-3
[3] Cenzer, D.: Effective dynamics. In: Crossley, J., Remmel, J., Shore, R., Sweedler, M. (eds.) Logical Methods in Honor of Anil Nerode’s Sixtieth Birthday, pp. 162–177. Birkhäuser, Basel (1993) · Zbl 0810.00003
[4] Cenzer, D.: $\(\backslash\)Pi\^{0}_{1}$ classes in computability theory. In: Griffor, E. (ed.) Handbook of Computability Theory. Elsevier Studies in Logic, vol. 140, pp. 37–85 (1999) · Zbl 0939.03047
[5] Cenzer, D., Clote, P., Smith, R., Soare, R., Wainer, S.: Members of countable $\(\backslash\)Pi\^{0}_{1}$ classes. Ann. Pure Appl. Log. 31, 145–163 (1986) · Zbl 0605.03020 · doi:10.1016/0168-0072(86)90067-9
[6] Cenzer, D., Dashti, A., King, J.L.F.: Computable symbolic dynamics. Math. Log. Q. 54, 524–533 (2008) · Zbl 1170.03029
[7] Cenzer, D., Dashti, A., Toska, F., Wyman, S.: Computability of countable shifts. In: Ferreira, F., et al. (eds.) Programs, Proofs and Processes, CIE 2010. Springer Lecture Notes in Computer Science, vol. 6158, pp. 88–97 (2010) · Zbl 1285.03054
[8] Cenzer, D., Downey, R., Jockusch, C.G., Shore, R.: Countable thin $\(\backslash\)Pi\^{0}_{1}$ classes. Ann. Pure Appl. Log. 59, 79–139 (1993) · Zbl 0909.03039 · doi:10.1016/0168-0072(93)90001-T
[9] Cenzer, D., Hinman, P.G.: Degrees of difficulty of generalized r.e. separating classes. Arch. Math. Log. 45, 629–647 (2008) · Zbl 1151.03020 · doi:10.1007/s00153-007-0058-y
[10] Cenzer, D., Remmel, J.B.: $\(\backslash\)Pi\^{0}_{1}$ classes. In: Ersov, Y., Goncharov, S., Marek, V., Nerode, A., Remmel, J. (eds.) Handbook of Recursive Mathematics, Vol. 2: Recursive Algebra, Analysis and Combinatorics. Elsevier Studies in Logic and the Foundations of Mathematics, vol. 139, pp. 623–821 (1998)
[11] Cenzer, D., Smith, R.: The ranked points of a $\(\backslash\)Pi\^{0}_{1}$ set. J. Symb. Log. 54, 975–991 (1989) · Zbl 0689.03022 · doi:10.2307/2274757
[12] Delvenne, J.-C., Kurka, P., Blondel, V.: Decidability and universality in symbolic dynamical systems. Fundam. Inform. 74, 463–490 (2006) · Zbl 1114.03032
[13] Hochman, M.: On the dynamics and recursive properties of multidimensional symbolic systems. Invent. Math. 176, 131–167 (2009) · Zbl 1168.37002 · doi:10.1007/s00222-008-0161-7
[14] Ko, K.: On the computability of fractal dimensions and Julia sets. Ann. Pure Appl. Log. 93, 195–216 (1998) · Zbl 0926.03049 · doi:10.1016/S0168-0072(97)00060-2
[15] Lothaire, M.: Algebraic Combinatorics on Words. Encyclopedia of Math. and its Appl., vol. 90. Cambridge University Press, Cambridge (2002) · Zbl 1001.68093
[16] Medvedev, Y.: Degrees of difficulty of the mass problem. Dokl. Akad. Nauk SSSR 104, 501–504 (1955)
[17] Miller, J.: Two notes on subshifts. Proc. Am. Math. Soc. (to appear) · Zbl 1246.37025
[18] Rettinger, R., Weihrauch, K.: The computational complexity of some Julia sets. In: Goemans, M.X. (ed.) Proc. 35th ACM Symposium on Theory of Computing, San Diego, June 2003, pp. 177–185. ACM, New York (2003) · Zbl 1192.68375
[19] Simpson, S.G.: Mass problems and randomness. Bull. Symb. Log. 11, 1–27 (2005) · Zbl 1090.03015 · doi:10.2178/bsl/1107959497
[20] Simpson, S.G.: Subsystems of Second Order Arithmetic, 2nd edn. Cambridge University Press, Cambridge (2009) · Zbl 1181.03001
[21] Simpson, S.G.: Medvedev degrees of two-dimensional subshifts of finite type. Ergod. Theory Dyn. Syst. (to appear) · Zbl 1351.37053
[22] Sorbi, A.: The Medvedev lattice of degrees of difficulty. In: Cooper, S.B., et al. (eds.) Computability, Enumerability, Unsolvability: Directions in Recursion Theory. London Mathematical Society Lecture Notes, vol. 224, pp. 289–312. Cambridge University Press, Cambridge (1996). ISBN 0-521-55736-4 · Zbl 0849.03033
[23] Weihrauch, K.: Computable Analysis. Springer, Berlin (2000) · Zbl 0956.68056
[24] Jeandal, E., Vanier, P.: Turing degrees of multidimensional SFTs. arXiv:1108.1012v1 · Zbl 1417.03241
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.