Computability Theoretic Properties of the Entropy of Gap Shifts

Article type: Research Article

Authors: Hertling, Peter | Spandl, Christoph

Affiliations: Institut für Theoretische Informatik und Mathematik, Fakultät für Informatik, Universität der Bundeswehr München 85577 Neubiberg, Germany. E-mails: [email protected]; [email protected]

Abstract: First, we analyse the computability theoretic relationship between the defining set S of a "gap shift" and the language of the gap shift. Therefore, we look at various computability theoretic conditions that the set S of a gap shift or the language of a gap shift might satisfy: decidability, computable enumerability, and computable enumerability of the complement. Then we look at the topological entropy of a gap shift and analyse the relationship between on the one hand the various kinds of computability theoretic conditions on a gap shift that we just mentioned and on the other hand various kinds of computability theoretic conditions on the entropy resp. on any real number in the unit interval: computability, left-computability, and right-computability.

Journal: Fundamenta Informaticae, vol. 83, no. 1-2, pp. 141-157, 2008