Dominoes.

The aperiodic Domino problem

The classical Domino problem asks whether there exists a tiling in which none of the forbidden patterns given as input appear. In this talk, we consider the aperiodic version of the Domino problem: given as input a family of forbidden patterns, does it allow an aperiodic tiling? The input may correspond to a subshift of finite type, a sofic subshift or an effective subshift.

The Aperiodic Domino is undecidable, because it reduces to the (classical) Domino problem. In this talk, we study the computational complexity of the Aperiodic Domino problem: \(\Pi_1^0\)-complete for \(\mathbb{Z}^2\) subshifts (by a result from A. Grandjean, B. Hellouin and P. Vanier), it becomes \(\Sigma_1^1\)-complete (ie. much harder, namely analytic) in higher dimension: \(d \geq 4\) in the finite type case, \(d \geq 3\) for sofic and effective subshifts.

These results are surprising for two reasons: first, the Aperiodic Domino separates 2- and 3-dimensional subshifts, wheareas most subshift properties are the same in dimension 2 and higher; second, this gap unexpectedly large.

For more details, you can read the associated article!