×

zbMATH — the first resource for mathematics

The undecidability of the domino problem. (English) Zbl 07287528
Akiyama, Shigeki (ed.) et al., Substitution and tiling dynamics: introduction to self-inducing structures. Lecture notes from the research school on tiling dynamical systems, CIRM Jean-Morlet Chair, Marseille, France, Fall 2017. Cham: Springer (ISBN 978-3-030-57665-3/pbk; 978-3-030-57666-0/ebook). Lecture Notes in Mathematics 2273, 293-357 (2020).
Summary: One of the most fundamental problems in tiling theory is to decide, given a surface, a set of tiles and a tiling rule, whether there exists a way to tile the surface using the set of tiles and following the rules. As proven by R. Berger [The undecidability of the domino problem. Boston: Harvard University (PhD. thesis) (1964); see also Zbl 0199.30802] in the 1960s, this problem is undecidable in general. When formulated in terms of tilings of the discrete plane \(\mathbb{Z}^2\) by unit tiles with colored constraints, this is called the Domino Problem and was introduced by H. Wang [“Proving theorems by pattern recognition II”, Bell Syst. Tech. J. 40, No. 1, 1–41 (1961; doi:10.1002/j.1538-7305.1961.tb03975.x)] in an effort to solve satisfaction problems for \(\forall \exists \forall\) formulas by translating the problem into a geometric problem. There exist a few different proofs of this result. The most well-known proof is probably the proof by R. M. Robinson [Invent. Math. 12, 177–209 (1971; Zbl 0197.46801)] which is a variation on the proof of Berger. A relatively new proof by J. Kari [Lect. Notes Comput. Sci. 4664, 72–79 (2007; Zbl 1211.03062)] has some nice ramifications for tilings of surfaces and groups. In terms of ingredients, one can divide the proofs in 4 categories. The remaining two categories are given by the proof of S. O. Aanderaa and H. R. Lewis [J. Symb. Log. 39, 519–548 (1974; Zbl 0301.02042)] and the fixed point method of B. Durand et al. [J. Comput. Syst. Sci. 78, No. 3, 731–764 (2012; Zbl 1244.05049)]. In this course, we will give a brief description of the problem and to the meaning of the word “undecidable”, and then give the four different proofs. As we will explain, the undecidability of the Domino Problem has as a consequence the existence of an aperiodic tileset. All four sections will be organized in such a way that the interested reader can first extract from the proof the aperiodic tileset into consideration, before we go into more details to actually prove the undecidability of the problem.
For the entire collection see [Zbl 1454.37001].
MSC:
52C20 Tilings in \(2\) dimensions (aspects of discrete geometry)
37B52 Tiling dynamics
52C23 Quasicrystals and aperiodic tilings in discrete geometry
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] S.O. Aanderaa, H.R. Lewis, Linear sampling and the ∀∃∀ case of the decision problem. J. Symb. Log. 39(3), 519-548 (1974). See also [H.R. Lewis, Unsolvable Classes of Quantificational Formulas (Addison-Wesley, Reading, 1979)] · Zbl 0301.02042
[2] C. Allauzen, B. Durand, Tiling problems. in The Classical Decision Problem, Perspectives in Mathematical Logic, chap. A (Springer, Berlin, 2001), pp. 407-420
[3] R. Ammann, B. Grunbaum, G. Shephard, Aperiodic tiles. Discret. Comput. Geom. 8(1), 1-25 (1992) · Zbl 0758.52013
[4] S. Arora, B. Barak, Computational Complexity: A Modern Approach, 1st edn (Cambridge University Press, New York, 2009) · Zbl 1193.68112
[5] A. Ballier, Propriétés structurelles, combinatoires et logiques des pavages. Ph.D. thesis, Aix-Marseille Université (2009)
[6] S. Beatty, Problem 3173. Am. Math. Mon. 33, 159 (1926) · JFM 52.0189.01
[7] R. Berger, The Undecidability of the Domino Problem. Ph.D. thesis, Harvard University (1964) · Zbl 0199.30802
[8] R. Berger, The Undecidability of the Domino Problem. No. 66 in Memoirs of the American Mathematical Society (The American Mathematical Society, Providence, 1966)
[9] J.R. Büchi, Turing-Machines and the Entscheidungsproblem. Math. Ann. 148(3), 201-213 (1962). https://doi.org/10.1007/BF01470748 · Zbl 0118.01602
[10] J.R. Chazottes, J.M. Gambaudo, F. Gautero, Tilings of the plane and Thurston semi-norm. Geom. Dedicata 173(1), 129-142 (2014). https://doi.org/10.1007/s10711-013-9932-4 · Zbl 1316.52028
[11] A. Church, An unsolvable problem of elementary number theory. Am. J. Math. 58(2), 345-363 (1936) · Zbl 0014.09802
[12] P. Collins, J.H. van Schuppen, Observability of hybrid systems and turing machines, in 43rd IEEE Conference on Decision and Control (2004), pp. 7-12. https://doi.org/0.1109/CDC.2004.1428598
[13] B. Durand, L.A. Levin, A. Shen, Local rules and global order, or aperiodic tilings. Math. Intell. 27(1), 64-68 (2004) · Zbl 1066.52501
[14] B. Durand, A. Romashchenko, A. Shen, Fixed-point tile sets and their applications. J. Comput. Syst. Sci. 78(3), 731-764 (2012). https://doi.org/10.1016/j.jcss.2011.11.001 · Zbl 1244.05049
[15] B. Durand, A. Shen, A. Romashchenko, Fixed Point and Aperiodic Tilings. Tech. Rep. TR08-030, ECCC (2008) · Zbl 1161.68033
[16] S. Eigen, J. Navarro, V.S. Prasad, An aperiodic tiling using a dynamical system and Beatty sequences, in Recent Progress in Dynamics. MSRI Publications, vol. 54 (Cambridge University Press, Cambridge, 2007) · Zbl 1215.52008
[17] T. Fernique, N. Ollinger, Combinatorial substitutions and Sofic Tilings , in Journées Automates Cellulaires (JAC), TUCS (2010), pp. 100-110
[18] N.P. Fogg, in Substitutions in Dynamics, Arithmetics and Combinatorics, chap. Sturmian Sequences. Lecture Notes in Mathematics (Springer, Berlin, 2002)
[19] F. Gähler, A. Julien, J. Savinien, Combinatorics and Topology of the Robinson Tiling. Comptes Rendus de l’Académie des Sciences de Paris, Série I—Mathématiques (2012), pp. 627-631. https://doi.org/10.1016/j.crma.2012.06.007 · Zbl 1248.37023
[20] C. Goodman-Strauss, Matching rules and substitution tilings. Ann. Math. 147(1), 181-223 (1998) · Zbl 0941.52018
[21] W. Hanf, Non recursive tilings of the plane I. J. Symbolic Log. 39(2), 283-285 (1974) · Zbl 0299.02054
[22] F.C. Hennie, R.E. Stearns, Two-tape simulation of multitape turing machines. J. ACM 13(4), 533-546 (1966). https://doi.org/10.1145/321356.321362 · Zbl 0148.24801
[23] M. Hochman, On the dynamics and recursive properties of multidimensional symbolic systems. Invent. Math. 176(1), 2009 (2009) · Zbl 1168.37002
[24] M. Hochman, T. Meyerovitch, A characterization of the entropies of multidimensional shifts of finite type. Ann. Math. 171(3), 2011-2038 (2010). https://doi.org/10.4007/annals.2010.171.2011 · Zbl 1192.37022
[25] P.K. Hooper, The undecidability of the turing machine immortality problem. J. Symbolic Log. 31(2), 219-234 (1966) · Zbl 0173.01201
[26] J.E. Hopcroft, J.D. Ullman, Introduction to Automata Theory, Languages and Computation (Addison-Wesley, Reading, 1979) · Zbl 0426.68001
[27] E. Jeandel, M. Rao, An aperiodic set of 11 Wang tiles. Preprint
[28] A. Johnson, K. Madden, Putting the pieces together: understanding Robinson’s nonperiodic tilings. Coll. Math. J. 28(3), 172-181 (1997) · Zbl 0995.52506
[29] A. Kahr, E.F. Moore, H. Wang, Entscheidungsproblem reduced to the ∀∃∀ case. Proc. Natl. Acad. Sci. U. S. A. 48(3), 365-377 (1962) · Zbl 0102.00801
[30] J. Kari, The nilpotency problem of one-dimensional cellular automata. SIAM J. Comput. 21(3), 571-586 (1992) · Zbl 0761.68067
[31] J. Kari, A small aperiodic set of Wang tiles. Discret. Math. 160, 259-264 (1996) · Zbl 0861.05017
[32] J. Kari, The tiling problem revisited, in Machines, Computations, and Universality (MCU). Lecture Notes in Computer Science, vol. 4664 (2007), pp. 72-79 · Zbl 1211.03062
[33] J. Kari, N. Ollinger, Periodicity and immortality in reversible computing, in MFCS 2008. Lecture Notes in Computer Science, vol. 5162 (2008), pp. 419-430 · Zbl 1173.68521
[34] S. Kleene, Two papers on the predicate calculus., chap., in Finite Axiomatizability of Theories in the Predicate Calculus Using Additional Predicate Symbols. No. 10 in Memoirs of the American Mathematical Society (American Mathematical Society, Providence, 1952) · Zbl 0047.25001
[35] L.A. Levin, Forbidden information. J. ACM 60(2), 9:1-9 (2013). https://doi.org/10.1145/2450142.2450145 · Zbl 1281.68139
[36] H.R. Lewis, Unsolvable Classes of Quantificational Formulas (Addison-Wesley, Reading, 1979) · Zbl 0423.03003
[37] H.R. Lewis, C.H. Papadimitriou, Elements of the Theory of Computation (Prentice-Hall, Englewood Cliffs, 1998)
[38] D.A. Lind, B. Marcus, An Introduction to Symbolic Dynamics and Coding (Cambridge University Press, New York, 1995) · Zbl 1106.37301
[39] M.L. Minsky, Computation: Finite and Infinite Machines (Prentice-Hall, Englewood Cliffs, 1967) · Zbl 0195.02402
[40] S. Mozes, Tilings, substitutions systems and dynamical systems generated by them. J. Anal. Math. 53, 139-186 (1989) · Zbl 0745.52013
[41] D. Myers, Non recursive tilings of the plane II. J. Symbolic Log. 39(2), 286-294 (1974) · Zbl 0299.02055
[42] R. Nillsen, K. Tognetti, G. Winley, Bernoulli (Beta) and Integer Part Sequences (Australian Mathematical Society, Canberra, 1999)
[43] N. Ollinger, Two-by-two substitution systems and the undecidability of the domino problem, in CiE 2008. Lecture Notes in Computer Science, vol. 5028 (2008), pp. 476-485 · Zbl 1142.03357
[44] C.H. Papadimitriou, Computational Complexity (Addison Wesley, Reading, 1995) · Zbl 0557.68033
[45] B. Poizat, Une théorie finiement axiomatisable et superstable. Groupe d’études de théories stables 3, 1-9 (1980)
[46] R.M. Robinson, Seven polygons which permit only nonperiodic tilings of the plane. Not. Am. Math. Soc. 14, 835 (1967)
[47] R.M. Robinson, Undecidability and nonperiodicity for tilings of the plane. Invent. Math. 12(3), 177-209 (1971). https://doi.org/10.1007/BF01418780 · Zbl 0197.46801
[48] O. Salon, Quelles tuiles! (Pavages apériodiques du plan et automates bidimensionnels). J. Théor. Nombres Bordeaux 1(1), 1-26 (1989) · Zbl 0726.11020
[49] S.G. Simpson, Medvedev degrees of two-dimensional subshifts of finite type. Ergodic Theory Dynam. Syst. 34, 679-688 (2014). https://doi.org/10.1017/etds.2012.152 · Zbl 1351.37053
[50] A.M. Turing, On computable numbers, with an application to the entscheidungsproblem. Proc. Lond. Math. Soc. s2-42(1), 230-265 (1937) · JFM 62.1059.03
[51] H. Wang, Proving theorems by pattern recognition II. Bell Syst. Tech. J. 40, 1-41 (1961)
[52] H. Wang, Dominoes and the ∀∃∀ case of the decision problem, in Mathematical Theory of Automata (1963), pp. 23-55
[53] L.B. Westrick, Seas of squares with sizes from a \(\varPi^0_1\) set. Isr. J. Math. 222(1), 431-462 (2017). https://doi.org/10.1007/s11856-017-1596-6 · Zbl 1416.37021
[54] C.
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.