Computability Theoretic Properties of the Entropy of Gap Shifts

• Autorzy: Hertling, P. , Spandl, C.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

shifts; gap shifts; languages of shifts

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 83, nr 1-2
• Strony: 141-157
• Opis fizyczny: bibliogr. 9 poz.

Twórcy

autor

Hertling, P.

autor

Spandl, C.

• Institut für Theoretische Informatik,und Mathematik, Fakultät für Informatik, Universität der Bundeswehr München, 85577 Neubiberg, Germany,

Bibliografia

• [1] V. Brattka and P. Hertling. Topological properties of real number representations. Theoretical Computer Science, 284(2):241-257,2002.
• [2] P. Hertling and C. Spandl. Shifts with decidable language and non-computable entropy. Submitted for publication, March 2007.
• [3] D. Lind and B. Marcus. Symbolic Dynamics and Coding. Cambridge University Press, Cambridge, UK, 1995.
• [4] J. Milnor. Is entropy effectively computable? Remark, see http://www.math.sunysb.edu/~jack/comp-ent.pdf, 2002
• [5] J. G. Simonsen. On the computability of the topological entropy of subshifts. Discrete Mathematics and Theoretical Computer Science, 6:83-96, 2006.
• [6] R. Soare. Cohesive sets and recursively enumerable Dedekind cuts. Pacific J. Math., 31:215-231, 1969.
• [7] R. I. Soare. Recursively Enumerable Sets and Degrees. Springer, Berlin, 1987.
• [8] C. Spandl. Computing the topological entropy of shifts. Mathematical Logic Quarterly, 53(4-5):493-510, 2007.
• [9] K. Weihrauch. Computable Analysis. Springer, Berlin, 2000