The aperiodic Domino problem in higher dimension
Le problème du Domino apériodique en dimension supérieure
Résumé
The classical Domino problem asks whether there exists a tiling in which none of the forbidden patterns given as input appear. In this paper, 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. [8] proved that this problem is co-recursively enumerable (Π 1 0-complete) in dimension 2 for geometrical reasons. We show that it is much harder, namely analytic (Σ 1 1-complete), in higher dimension: d ≥ 4 in the finite type case, d ≥ 3 for sofic and effective subshifts. The reduction uses a subshift embedding universal computation and two additional dimensions to control periodicity. This complexity jump is surprising for two reasons: first, it separates 2-and 3-dimensional subshifts, whereas most subshift properties are the same in dimension 2 and higher; second, it is unexpectedly large.
Origine : Fichiers produits par l'(les) auteur(s)
