Computability of topological pressure on compact shift spaces beyond finite type*
- 29 June 2022
- journal article
- research article
- Published by IOP Publishing in Nonlinearity
- Vol. 35 (8) , 4250-4282
Abstract
We investigate the computability (in the sense of computable analysis) of the topological pressure P top(ϕ) on compact shift spaces X for continuous potentials ϕ : X → R . This question has recently been studied for subshifts of finite type (SFTs) and their factors (sofic shifts). We develop a framework to address the computability of the topological pressure on general shift spaces and apply this framework to coded shifts. In particular, we prove the computability of the topological pressure for all continuous potentials on S-gap shifts, generalised gap shifts, and particular beta-shifts. We also construct shift spaces which, depending on the potential, exhibit computability and non-computability of the topological pressure. We further prove that the generalised pressure function (X, ϕ) ↦ P top(X, ϕ| X ) is not computable for a large set of shift spaces X and potentials ϕ. In particular, the entropy map X ↦ h top(X) is computable at a shift space X if and only if X has zero topological entropy. Along the way of developing these computability results, we derive several ergodic-theoretical properties of coded shifts which are of independent interest beyond the realm of computability.Keywords
All Related Versions
Funding Information
- Simons Foundation (637594)
- Division of Mathematical Sciences (1913119)
- Division of Computing and Communication Foundations (1527193)
This publication has 43 references indexed in Scilit:
- Dynamics and abstract computability: Computing invariant measuresDiscrete and Continuous Dynamical Systems, 2011
- A characterization of the entropies of multidimensional shifts of finite typeAnnals of Mathematics, 2010
- Equilibrium measures for maps with inducing schemesJournal of Modern Dynamics, 2008
- Computing the topological entropy of shiftsMathematical Logic Quarterly, 2007
- Parabolic Julia sets are polynomial time computableNonlinearity, 2006
- Finitely generated sofic systemsTheoretical Computer Science, 1989
- Chains, entropy, codingErgodic Theory and Dynamical Systems, 1986
- The entropies of topological Markov shifts and a related class of algebraic integersErgodic Theory and Dynamical Systems, 1984
- On theβ-expansions of real numbersActa Mathematica Hungarica, 1960
- Representations for real numbers and their ergodic propertiesActa Mathematica Hungarica, 1957