F Nous contacter

Multi angle

H 1 The undecidability of the domino problem

Auteurs : Jeandel, Emmanuel (Auteur de la Conférence)
CIRM (Editeur )

    Loading the player...

    Résumé : 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.

    Codes MSC :
    03D35 - Undecidability and degrees of sets of sentences
    05B45 - Tessellation and tiling problems

      Informations sur la Vidéo

      Réalisateur : Hennenfent, Guillaume
      Langue : Anglais
      Date de publication : 28/11/2017
      Date de captation : 21/11/2017
      Collection : Research schools
      Format : MP4
      Durée : 01:06:53
      Domaine : Logic and Foundations ; Combinatorics
      Audience : Chercheurs ; Etudiants Science Cycle 2 ; Doctorants , Post - Doctorants
      Download : https://videos.cirm-math.fr/2017-11-21_Jeandel.mp4

    Informations sur la rencontre

    Nom du congrès : Jean-Morlet chair - Research school: Tiling dynamical system / Chaire Jean-Morlet - École de recherche : Pavages et systèmes dynamiques
    Organisteurs Congrès : Akiyama, Shigeki ; Arnoux, Pierre
    Dates : 20/11/2017 - 24/11/2017
    Année de la rencontre : 2017
    URL Congrès : https://akiyama-arnoux.weebly.com/school.html

    Citation Data

    DOI : 10.24350/CIRM.V.19248603
    Cite this video as: Jeandel, Emmanuel (2017). The undecidability of the domino problem. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19248603
    URI : http://dx.doi.org/10.24350/CIRM.V.19248603

    Voir aussi


    1. Berger, R. (1966). The undecidability of the domino problem. Memoirs of the American Mathematical Society, 66, 72 p. - http://www.ams.org/books/memo/0066/