The Undecidability of the Domino Problem

International audienceThe Undecidability of the Domino ProblemEmmanuel Jeandel and Pascal VanierOne of the most fundamental problem in tiling theory is to decide, given a surface,a set of tiles and a tiling rule, whether there exist a way to tile the surface using theset of tiles and following the rules. As proven by Berger [7] in the 60’s, this problemis undecidable in general.When formulated in terms of tilings of the discrete planeZ2by unit tiles withcolored constraints, this is called the Domino Problem and was introduced by Wang[51] in an effort to solve satisfaction problems for∀∃∀formulas by translating theproblem into a geometric problem.There exist a few different proofs of this result. The most well-known proof isprobably the proof by Robinson [47] which is a variation on the proof of Berger. Arelatively new proof by Kari [32] has some nice ramifications for tilings of surfacesand groups. In terms of ingredients, one can divide the proofs in 4 categories. Theremaining two categories are given by the proof of Aanderaa and Lewis[1] and theFixed point method of Durand, Romashchenko and Shen [14].In this course, we will give a brief description of the problem and to the mean-ing of the word “undecidable”, and then give the four different proofs. As we willexplain soon, the undecidability of the Domino Problem has as a consequence theexistence of an aperiodic tileset. All four sections will be organized in such a waythat the interested reader can first extract from the proof the aperiodic tileset intoconsideration, before we go into more details to actually prove the undecidability ofthe problem