论文标题
嘈杂瓷砖的Besicovitch稳定性的算术层次结构
Arithmetical Hierarchy of the Besicovitch-Stability of Noisy Tilings
论文作者
论文摘要
本文的目的是研究有限类型的嘈杂次要换档的besicovitch稳定性的算法复杂性，这是上一篇文章中研究的一个概念。首先，我们表现出不稳定的大道瓷砖，然后看看它如何用作构建基础，以实施从图灵机上经典不可确定的问题来实施几项减少。随之而来的是，有限类型的稳定性的稳定性是不可确定的，并且我们在算术层次结构中获得的最强下限是$π_2$ -HARDNESS。最后，我们证明，这个决策问题需要通过一组不可数的概率度量进行量化，具有$π_4$上限。
The purpose of this article is to study the algorithmic complexity of the Besicovitch stability of noisy subshifts of finite type, a notion studied in a previous article. First, we exhibit an unstable aperiodic tiling, and then see how it can serve as a building block to implement several reductions from classical undecidable problems on Turing machines. It will follow that the question of stability of subshifts of finite type is undecidable, and the strongest lower bound we obtain in the arithmetical hierarchy is $Π_2$-hardness. Lastly, we prove that this decision problem, which requires to quantify over an uncountable set of probability measures, has a $Π_4$ upper bound.
