Turing degree spectra of minimal subshifts
From MaRDI portal
Publication:2399371
DOI10.1007/978-3-319-58747-9_15zbMath1491.03031arXiv1408.6487OpenAlexW2963410372MaRDI QIDQ2399371
Pascal Vanier, Michael Hochman
Publication date: 22 August 2017
Full work available at URL: https://arxiv.org/abs/1408.6487
Symbolic dynamics (37B10) Other degrees and reducibilities in computability and recursion theory (03D30)
Related Items
Computability in Symbolic Dynamics, Cototal enumeration degrees and their applications to effective mathematics, Computability of topological pressure on compact shift spaces beyond finite type*, Quasiperiodicity and Non-computability in Tilings, The relationship between word complexity and computational complexity in subshifts, The expressiveness of quasiperiodic and minimal shifts of finite type, Characterizing entropy dimensions of minimal mutidimensional subshifts of finite type, Quantified block gluing for multidimensional subshifts of finite type: aperiodicity and entropy, On the Expressive Power of Quasiperiodic SFT.
Cites Work
- Simulation of effective subshifts by two-dimensional subshifts of finite type
- Turing degrees of multidimensional SFTs
- Computability of countable subshifts in one dimension
- A characterization of the entropies of multidimensional shifts of finite type
- On the dynamics and recursive properties of multidimensional symbolic systems
- On the degree spectrum of a $\Pi ^0_1$ class
- Notes on Renewal Systems
- Computable symbolic dynamics
- Tilings Robust to Errors
- Computability of Countable Subshifts
- Periodicity in Tilings
- Effective Closed Subshifts in 1D Can Be Implemented in 2D
- Nonrecursive tilings of the plane. I
- Nonrecursive tilings of the plane. II
- Algorithmic Complexity for the Realization of an Effective Subshift By a Sofic.
- An Introduction to Symbolic Dynamics and Coding
- Two notes on subshifts
- Symbolic Dynamics II. Sturmian Trajectories