Shifts with Decidable Language and Non-Computable Entropy
Shifts with Decidable Language and Non-Computable Entropy
复制标题
可判定语言和不可计算熵的变化
DOI：
--
复制
发表时间：
2008
影响因子：
0.7
通讯作者：
C. Spandl
中科院分区：
文献类型：
--
作者：
P. Hertling;C. Spandl
我们考虑二元双无限序列的全移位的子移位。一方面，任何可计算余序语言的子移位的拓扑熵是0到1之间的右可计算真实的数。另一方面，我们证明了0到1之间的任何右可计算的真实的数，无论是否可计算，都是具有偶数多项式时间可判定语言的子移位的熵。此外，我们表明，子移位的熵的可计算性并不意味着任何类型的子移位的语言的可计算性
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