Jean-Morlet chair - Research school: Tiling dynamical system / Chaire Jean-Morlet - École de recherche : Pavages et systèmes dynamiques

Collection Jean-Morlet chair - Research school: Tiling dynamical system / Chaire Jean-Morlet - École de recherche : Pavages et systèmes dynamiques

Organizer(s) Akiyama, Shigeki ; Arnoux, Pierre

Date(s) 20/11/2017 - 24/11/2017

linked URL https://www.chairejeanmorlet.com/1720.html

00:00:00 / 00:00:00

2 5

The undecidability of the domino problem

By Emmanuel Jeandel

Also appears in collection : Ecoles de recherche

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.

Information about the video

Date of recording 21/11/2017
Date of publication 28/11/2017
Institution CIRM
Licence CC BY NC ND
Language English
Audience Researchers, Graduate Students
Director(s) Guillaume Hennenfent
Format MP4

Citation data

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

Domain(s)

Bibliography

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/

MSC codes

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow

All the collection videos

01:20:19

published on November 28, 2017

Introduction to hierarchical tiling dynamical systems: Supertile construction methods

By Natalie Priebe Frank

01:06:53

published on November 28, 2017

The undecidability of the domino problem

By Emmanuel Jeandel

01:28:30

published on November 28, 2017

From combinatorial games to shape-symmetric morphisms

By Michel Rigo

01:38:52

published on November 28, 2017

$S$-adic sequences: a bridge between dynamics, arithmetic, and geometry

By Jörg Thuswaldner

01:21:20

published on November 28, 2017

Lecture on Delone sets and tilings

By Boris Solomyak

Copyright Carmin.tv 2024

Give feedback