zbMATH — the first resource for mathematics

Turing degrees of multidimensional SFTs. (English) Zbl 1417.03241
Summary: In this paper, we are interested in computability aspects of subshifts and in particular Turing degrees of two-dimensional subshifts of finite type (SFTs) (i.e., tilings). To be more precise, we prove that, given any \(\Pi_1^0\) class \(P\) of \(\{0,1\}^\mathbb N\), there is an SFT \(X\) such that \(P\times\mathbb Z^2\) is recursively homeomorphic to \(X\setminus U\), where \(U\) is a computable set of points. As a consequence, if \(P\) contains a computable member, \(P\) and \(X\) have the exact same set of Turing degrees. On the other hand, we prove that, if \(X\) contains only non-computable members, some of its members always have different but comparable degrees. This gives a fairly complete study of Turing degrees of SFTs.

03D28 Other Turing degree structures
37B10 Symbolic dynamics
52C20 Tilings in \(2\) dimensions (aspects of discrete geometry)
Full Text: DOI
[1] A. Ballier, B. Durand, E. Jeandel, Structural aspects of tilings, in: 25th International Symposium on Theoretical Aspects of Computer Science, STACS, 2008. · Zbl 1258.05023
[2] Ballier, A.; Jeandel, E., Computing (or not) quasi-periodicity functions of tilings, (Symposium on Cellular Automata (JAC), (2010)), 54-64
[3] R. Berger, The undecidability of the domino problem, Ph.D. Thesis, Harvard University, 1964. · Zbl 0199.30802
[4] Berger, R., (The Undecidability of the Domino Problem, Memoirs of the American Mathematical Society, vol. 66, (1966)) · Zbl 0199.30802
[5] Cenzer, D.; Dashti, A.; King, J. L.F., Computable symbolic dynamics, Mathematical Logic Quarterly, 54, 5, 460-469, (2008) · Zbl 1170.03029
[6] D. Cenzer, A. Dashti, F. Toska, S. Wyman, Computability of countable subshifts in one dimension. Theory of Computing Systems, 1-2010.1007/s00224-011-9358-z. 2012. http://dx.doi.org/10.1007/s00224-011-9358-z. · Zbl 1285.03055
[7] Cenzer, D.; Remmel, J., \(\Pi_1^0\) classes in mathematics, (Handbook of Recursive Mathematics - Volume 2: Recursive Algebra, Analysis and Combinatorics, Studies in Logic and the Foundations of Mathematics, vol. 139, (1998), Elsevier), 623-821, Ch. 13 · Zbl 0941.03044
[8] D. Cenzer, J. Remmel, Effectively closed sets, ASL Lecture Notes in Logic, 2011 (in preparation). · Zbl 1140.03026
[9] Culik, K., An aperiodic set of 13 Wang tiles, Discrete Mathematics, 160, 245-251, (1996) · Zbl 0865.05033
[10] A. Dashti, Effective symbolic dynamics, Ph.D. Thesis, University of Florida, 2008. · Zbl 1262.37008
[11] Durand, B., Tilings and quasiperiodicity, Theoretical Computer Science, 221, 1-2, 61-75, (1999) · Zbl 1062.05502
[12] Durand, B.; Levin, L. A.; Shen, A., Complex tilings, Journal of Symbolic Logic, 73, 2, 593-613, (2008) · Zbl 1141.03021
[13] Hanf, W., Non recursive tilings of the plane I, Journal of Symbolic Logic, 39, 2, 283-285, (1974) · Zbl 0299.02054
[14] Jockusch, C. G.; Soare, R. I., Degrees of members of \(\Pi_1^0\) classes, Pacific Journal of Mathematics, 40, 605-616, (1972) · Zbl 0209.02201
[15] Jockusch, C. G.; Soare, R. I., \(\Pi_1^0\) classes and degrees of theories, Transactions of the American Mathematical Society, 173, 33-56, (1972) · Zbl 0262.02041
[16] Kari, J., A small aperiodic set of Wang tiles, Discrete Mathematics, 160, 259-264, (1996) · Zbl 0861.05017
[17] Kechris, A. S., Classical descriptive set theory, (Graduate Texts in Mathematics, vol. 156, (1995), Springer-Verlag New York) · Zbl 0819.04002
[18] Lind, D., Multi-dimensional symbolic dynamics, Proceedings of Symposia in Applied Mathematics, 60, 81-120, (2004)
[19] Lind, D.; Marcus, B., An introduction to symbolic dynamics and coding, (1995), Cambridge University Press New York, NY, USA · Zbl 1106.37301
[20] Myers, D., Non recursive tilings of the plane II, Journal of Symbolic Logic, 39, 2, 286-294, (1974) · Zbl 0299.02055
[21] Robinson, R. M., Undecidability and nonperiodicity for tilings of the plane, Inventiones Mathematicae, 12, (1971) · Zbl 0197.46801
[22] Simpson, S. G., Mass problems associated with effectively closed sets, Tohoku Mathematical Journal. Second Series, 63, 4, 489-517, (2011-2012) · Zbl 1246.03064
[23] Simpson, S. G., Medvedev degrees of 2-dimensional subshifts of finite type, Ergodic Theory and Dynamical Systems, (2011)
[24] Wang, H., Proving theorems by pattern recognition II, Bell Systems Technical Journal, 40, 1-41, (1961)
[25] Wang, H., Dominoes and the \(\forall \exists \forall\) case of the decision problem, Mathematical Theory of Automata, 23-55, (1963)
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.