×

zbMATH — the first resource for mathematics

\(\Pi^{0}_{1}\) sets and tilings. (English) Zbl 1333.03109
Ogihara, Mitsunori (ed.) et al., Theory and applications of models of computation. 8th annual conference, TAMC 2011, Tokyo, Japan, May 23–25, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-20876-8/pbk). Lecture Notes in Computer Science 6648, 230-239 (2011).
Summary: In this paper, we prove that given any \(\Pi^{0}_{1}\) subset \(P\) of \(\{0,1\}^{\mathbb N}\) there is a tileset \(\tau \) with a countable set of configurations \(C\) such that \(P\) is recursively homeomorphic to \(C \setminus U\) where \(U\) is a computable set of configurations. As a consequence, if \(P\) is countable, this tileset has the exact same set of Turing degrees.
For the entire collection see [Zbl 1213.68052].

MSC:
03D28 Other Turing degree structures
03D15 Complexity of computation (including implicit computational complexity)
52C20 Tilings in \(2\) dimensions (aspects of discrete geometry)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ballier, A., Durand, B., Jeandel, E.: Structural aspects of tilings. In: 25th International Symposium on Theoretical Aspects of Computer Science (STACS) (2008) · Zbl 1258.05023
[2] Berger, R.: The Undecidability of the Domino Problem. PhD thesis, Harvard University (1964) · Zbl 0199.30802
[3] Berger, R.: The Undecidability of the Domino Problem. Memoirs of the American Mathematical Society, vol. 66. The American Mathematical Society, Providence (1966) · Zbl 0199.30802
[4] Cenzer, D., Dashti, A., King, J.L.F.: Computable symbolic dynamics. Mathematical Logic Quarterly 54(5), 460–469 (2008) · Zbl 1170.03029 · doi:10.1002/malq.200710066
[5] Cenzer, D., Dashti, A., Toska, F., Wyman, S.: Computability of Countable Subshifts. In: Ferreira, F., Löwe, B., Mayordomo, E., Mendes Gomes, L. (eds.) CiE 2010. LNCS, vol. 6158, pp. 88–97. Springer, Heidelberg (2010) · Zbl 1285.03054 · doi:10.1007/978-3-642-13962-8_10
[6] Cenzer, D., Remmel, J.B.: \(\Pi_1^0\) classes in mathematics. In: Handbook of Recursive Mathematics - Volume 2: Recursive Algebra, Analysis and Combinatorics, ch. 13. Studies in Logic and the Foundations of Mathematics, vol. 139, pp. 623–821. Elsevier, Amsterdam (1998) · Zbl 0941.03044 · doi:10.1016/S0049-237X(98)80046-3
[7] Cenzer, D., Remmel, J.: Effectively Closed Sets. ASL Lecture Notes in Logic (2011) (in preparation) · Zbl 1039.03033
[8] Dashti, A.: Effective Symbolic Dynamics. PhD thesis, University of Florida (2008) · Zbl 1262.37008
[9] Durand, B., Levin, L.A., Shen, A.: Complex tilings. Journal of Symbolic Logic 73(2), 593–613 (2008) · Zbl 1141.03021 · doi:10.2178/jsl/1208359062
[10] Hanf, W.: Non Recursive Tilings of the Plane I. Journal of Symbolic Logic 39(2), 283–285 (1974) · Zbl 0299.02054 · doi:10.2307/2272640
[11] Kechris, A.S.: Classical descriptive set theory. Graduate Texts in Mathematics, vol. 156. Springer, New York (1995) · Zbl 0819.04002 · doi:10.1007/978-1-4612-4190-4
[12] Lind, D., Marcus, B.: An introduction to symbolic dynamics and coding. Cambridge University Press, New York (1995) · Zbl 1106.37301 · doi:10.1017/CBO9780511626302
[13] Myers, D.: Non Recursive Tilings of the Plane II. Journal of Symbolic Logic 39(2), 286–294 (1974) · Zbl 0299.02055 · doi:10.2307/2272641
[14] Robinson, R.M.: Undecidability and Nonperiodicity for Tilings of the Plane. Inventiones Math. 12 (1971) · Zbl 0197.46801 · doi:10.1007/BF01418780
[15] Simpson, S.: Mass Problems Associated with Effectively Closed Sets (in preparation) · Zbl 1246.03064
[16] Simpson, S.G.: Medvedev Degrees of 2-Dimensional Subshifts of Finite Type. Ergodic Theory and Dynamical Systems (2011)
[17] Wang, H.: Proving theorems by Pattern Recognition II. Bell Systems Technical Journal 40, 1–41 (1961) · doi:10.1002/j.1538-7305.1961.tb03975.x
[18] Wang, H.: Dominoes and the 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.