论文标题
更高维度中的Aperiodic Domino问题
The aperiodic Domino problem in higher dimension
论文作者
论文摘要
经典的多米诺骨牌问题询问是否存在一个瓷砖，其中没有任何禁止的模式出现。在本文中，我们考虑了多米诺骨牌问题的多个多元版本：作为输入禁止模式的输入，它是否允许上的瓷砖？输入可能对应于有限类型，Sofic子换变或有效的子移位的子缩影。 ARXIV：1805.08829证明，出于几何原因，该问题在维度2中共同取得了枚举（$π_0^1 $ -COMPLETE）。我们表明，在有限类型的情况下，在更高的维度上，它更难，即分析（$σ_1^1 $ - $ -COMPLETE）：$ d \ geq 4 $，$ d \ geq 3 $用于SOFIC和有效的亚缩换。还原使用了一个嵌入通用计算的次班和两个额外的维度来控制周期性。这种复杂性的跳跃令人惊讶，原因有两个：首先，它分开了2-维的子迁移，而大多数subshift属性在维度2和更高的尺寸中相同；其次，它出乎意料的很大。
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. arXiv:1805.08829 proved that this problem is co-recursively enumerable ($Π_0^1$-complete) in dimension 2 for geometrical reasons. We show that it is much harder, namely analytic ($Σ_1^1$-complete), in higher dimension: $d \geq 4$ in the finite type case, $d \geq 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.
