Piecewise Affine Functions, Sturmian Sequences and Wang Tiles

Issue title: Discrete Mathematics (RuFiDiM 14)

Guest editors: J. Karhumäki, V. Mazalov and Yu. Matiyasevich

Article type: Research Article

Authors: Kari, Jarkko^*

Affiliations: Department of Mathematics and Statistics, FI-20014 University of Turku, Finland. [email protected]

Correspondence: [*] Address for correspondence: Department of Mathematics and Statistics, FI-20014 University of Turku, Finland

Abstract: 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 by Wang 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.

Keywords: Wang tiles, tiling problem, domino problem, Sturmian sequences, immortality problem, piecewise affine function, hyperbolic plane, aperiodicity

DOI: 10.3233/FI-2016-1360

Journal: Fundamenta Informaticae, vol. 145, no. 3, pp. 257-277, 2016