The undecidability of the domino problem


Among problems about 2D-subshifts, the domino problem is particularly well-known for its deep links with computability. It can be described as follows: given a finite set of pieces of jigsaw puzzle, is it possible to tile the whole plane (ie. \(\mathbb{Z}^2\)) with these pieces?

Although this problem was proved undecidable in 1966, it is still an active domain of research in the field of symbolic dynamics (the study of discrete dynamical systems). This field is at the intersection of mathematics and computer science, between topology and discrete algebra.

In this talk, we introduce the basics of symbolic dynamics and of subshifts, which are its most famous objects. After proving the domino problem undecidable with a classical proof due to [Robinson, 1977], we also present the proof of [Durand, Romashchenko and Shen, 2010] which relies on the so-called "fixpoint-based" tilesets. This will be the occasion to see how computability enables us to better undestand the nuances of this problem, which is nowadays a classic in discrete mathematics.