The undecidability of the domino problem
Apparaît également dans la collection : Jean-Morlet chair - Research school: Tiling dynamical system / Chaire Jean-Morlet - École de recherche : Pavages et systèmes dynamiques
One 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 the set of tiles and following the rules. As proven by Berger in the 60’s, this problem is undecidable in general. When formulated in terms of tilings of the discrete plane by unit tiles with colored constraints, this is called the Domino Problem and was introduced by Wang in an effort to solve satisfaction problems for ??? formulas by translating the problem into a geometric problem. In this course, we will give a brief description of the problem and to the meaning of the word “undecidable”, and then give two different proofs of the result.
