The fixed-point construction in tilings
Time: 14:00 -- Location: LRI, 445
summary: Consider a tileset, i.e. a finite set of colors along with some adjacency constraints between them.
It defines the set of colorings of the infinite grid that respects these adjacency constraints.
Such a coloring is called a tiling.
Given a tileset as input, a question naturally arises: does there exist a tiling that satisfies the given
adjacency constraints? This problem, called the "domino problem", was proven undecidable by R. Berger in [Berger, 1966].
This proof, as nearly all the subsequent proofs of undecidability, relies on geometric arguments to build
aperiodic infinite nested structures that can then embed universal computations.
Another construction by B. Durand, A. Romashchenko and A. Shen was introduced in [DRS, 2008]: instead of
geometrical arguments, it relies on Kleene's fixed-point theorem from computability. It builds an infinite
hierarchy of tilesets such that each level "simulates" the next one in the following sense: given a tiling
of level k, its tiles can be grouped together in squares that behave like a tiling of level k+1.
In its most basic form (when the hierarchy is constant), we obtain an aperiodic tiling that simulates itself.
In this talk, we present the fixed-point construction and several of its applications. Along with another proof
of undecidability of the domino problem, it has been used to obtain new proofs of computational characterizations
of tiling properties.