Discrete Mathematics & Theoretical Computer Science (Aug 2008)

Shifts with Decidable Language and Non-Computable Entropy

  • Peter Hertling,
  • Christoph Spandl

Journal volume & issue
Vol. 10, no. 3

Abstract

Read online

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.