Skip to Main content Skip to Navigation
Book sections

The Undecidability of the Domino Problem

Emmanuel Jeandel 1 Pascal Vanier 2, 3
1 MOCQUA - Designing the Future of Computational Models
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
3 Equipe AMACC - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen
Abstract : The 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.
Document type :
Book sections
Complete list of metadatas

https://hal.inria.fr/hal-03087341
Contributor : Emmanuel Jeandel <>
Submitted on : Wednesday, December 23, 2020 - 5:19:50 PM
Last modification on : Thursday, December 24, 2020 - 10:24:01 AM

Identifiers

Citation

Emmanuel Jeandel, Pascal Vanier. The Undecidability of the Domino Problem. Substitution and Tiling Dynamics: Introduction to Self-inducing Structures, 2273, pp.293-357, 2020, ⟨10.1007/978-3-030-57666-0_6⟩. ⟨hal-03087341⟩

Share

Metrics

Record views

19