Logic Workshop

May 3
Christian Wolf, CUNY
Computability of entropy and pressure on compact symbolic spaces beyond finite type

In this talk we discuss the computability of the entropy $H_{\rm top}(X)$ and topological pressure $P_{\rm top}(\phi)$ on compact shift spaces $X$ and continuous potentials $\phi:X\to\mathbb 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 entropy 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, generalized gap shifts, and Beta shifts. We also construct shift spaces which, depending on the potential, exhibit computability and non-computability of the topological pressure. We further show that the generalized pressure function $(X,\phi)\mapsto P_{\rm top}(X,\phi\vert_{X})$ is not computable for a large set of shift spaces $X$ and potentials $\phi$. 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. The topic of the talk is joint work with Michael Burr (Clemson U.), Shuddho Das (Texas Tech) and Yun Yang (Virginia Tech).