Discrete Mathematics & Theoretical Computer Science, Vol 10, No 3 (2008)

Font Size:  Small  Medium  Large

Shifts with Decidable Language and Non-Computable Entropy

Peter Hertling, Christoph Spandl

Abstract


We consider subshifts of the full shift of all binary bi-infinite sequences. On the one hand, the topological entropy of any subshift with computably co-enumerable language is a right-computable real number between 0 and 1. We show that, on the other hand, any right-computable real number between 0 and 1, whether computable or not, is the entropy of some subshift with even polynomial time decidable language. In addition, we show that computability of the entropy of a subshift does not imply any kind of computability of the language of the subshift.

Full Text: PostScript PDF