Piecewise Affine Functions, Sturmian Sequences and Wang Tiles

• Autorzy: Kari J.

Identyfikatory

DOI

10.3233/FI-2016-1360

• Języki publikacji: EN

Abstrakty

EN

The tiling problem is the decision problem to determine if the infinite plane can be tiled by copies of finitely many given Wang tiles. The problem is known since the 1960's to be undecidable. The undecidability is closely related to the existence of aperiodic Wang tile sets. There is a known method to construct small aperiodic tile sets that simulate iterations of one-dimensional piecewise linear functions using encodings of real numbers as Sturmian sequences. In this paper we provide details of a similar simulation of two-dimensional piecewise affine functions byWang tiles. Mortality of such functions is undecidable, which directly yields another proof of the undecidability of the tiling problem. We apply the same technique on the hyperbolic plane to provide a strongly aperiodic hyperbolic Wang tile set and to prove that the hyperbolic tiling problem is undecidable. These results are known in the literature but using different methods.

Słowa kluczowe

EN

aperiodicity; domino problem; hyperbolic plane; immortality problem; piecewise affine function; Sturmian sequences; tiling problem; Wang tiles

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 145, nr 3
• Strony: 257--277
• Opis fizyczny: Bibliogr. 15 poz., rys.

Twórcy

autor

Kari J.

• Department of Mathematics and Statistics, FI-20014 University of Turku, Finland

Bibliografia

• [1] Berger R. The Undecidability of the Domino Problem. American Mathematical Society memoirs. American Mathematical Society; 1966.
• [2] Robinson R. Undecidability and nonperiodicity for tilings of the plane. Inventiones Mathematicae. 1971;12:177–209.
• [3] Kari J. A small aperiodic set of Wang tiles. Discrete Mathematics. 1996;160(1-3):259 – 264. doi:http://dx.doi.org/10.1016/0012-365X(95)00120-L.
• [4] Culik K. An aperiodic set of 13 Wang tiles. Discrete Mathematics. 1996;160(1-3):245 – 251. doi:http://dx.doi.org/10.1016/S0012-365X(96)00118-5.
• [5] Margenstern M. The domino problem of the hyperbolic plane is undecidable. Theoretical Computer Science. 2008;407(1-3):29 – 84. doi:http://dx.doi.org/10.1016/j.tcs.2008.04.038.
• [6] Goodman-Strauss C. A strongly aperiodic set of tiles in the hyperbolic plane. Inventiones Mathematicae. 2005;159(1):119–132. doi:10.1007/s00222-004-0384-1.
• [7] Kari J. The Tiling Problem Revisited (Extended Abstract). In: Durand-Lose J, Margenstern M, editors. Machines, Computations, and Universality. vol. 4664 of Lecture Notes in Computer Science. Springer Berlin Heidelberg; 2007. p. 72–79. doi:10.1007/978-3-540-74593-8 6.
• [8] Blondel VD, Bournez O, Koiran P, Papadimitriou CH, Tsitsiklis JN. Deciding stability and mortality of piecewise affine dynamical systems. Theor Comput Sci. 2001;255(1-2):687–696.
• [9] Wang H. Proving Theorems by Pattern Recognition II. Bell System Technical Journal. 1961;40:1–42.
• [10] Hooper PK. The Undecidability of the Turing Machine Immortality Problem. J Symb Log. 1966;31(2):219–234.
• [11] Jeandel E. On Immortal Configurations in Turing Machines. In: Cooper SB, Dawar A, Lwe B, editors. How the World Computes. vol. 7318 of Lecture Notes in Computer Science. Springer Berlin Heidelberg; 2012. p.334–343. doi:10.1007/978-3-642-30870-3 34.
• [12] Koiran P, Cosnard M, Garzon M. Computability with low-dimensional dynamical systems. Theoretical Computer Science. 1994;132(1-2):113 – 128. doi:http://dx.doi.org/10.1016/0304-3975(94)90229-1.
• [13] Lothaire M. Algebraic combinatorics on words. Encyclopedia of mathematics and its applications. New York: Cambridge university press; 2002.
• [14] Grünbaum B, Shephard GC. Tilings and Patterns. New York, NY, USA: W. H. Freeman & Co.; 1986.
• [15] Aubrun N, Kari J. Tiling problems on Baumslag-Solitar groups. In: Neary T, Cook M, editors. Proceedings Machines, Computations and Universality 2013. vol. 128 of Electronic Proceedings in Theoretical Computer Science; 2013. p. 35–46.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).