Arithmetical Hierarchy of the Besicovitch-Stability of Noisy Tilings

Abstract

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 ${\Pi }_2$-hardness. Lastly, we prove that this decision problem, which requires to quantify over an uncountable set of probability measures, has a ${\Pi }_4$ upper bound.

arXiv comment37 pages, 8 figures

References in corpus (7)

• Reliable Cellular Automata with Self-Organization
• A Characterization of the Entropies of Multidimensional Shifts of Finite Type
• Simulation of Effective Subshifts by Two-dimensional Subshifts of Finite Type
• A generalization of the simulation theorem for semidirect products
• Topological completely positive entropy is no simpler in ${\mathbb{Z}}^2$-SFTs
• The aperiodic Domino problem in higher dimension
• On the Besicovitch-Stability of Noisy Random Tilings

Cited by in corpus (1)

• Characterisation of the Set of Ground States of Uniformly Chaotic Finite-Range Lattice Models