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