pith. sign in

arxiv: 1302.1170 · v1 · pith:6SXZSY4Vnew · submitted 2013-02-05 · 💻 cs.FL · cs.CC· cs.IT· math.DS· math.IT

Computability of the entropy of one-tape Turing Machines

classification 💻 cs.FL cs.CCcs.ITmath.DSmath.IT
keywords turingmachinesone-tapeentropyanymoreapproachapproximatebelief
0
0 comments X
read the original abstract

We prove that the maximum speed and the entropy of a one-tape Turing machine are computable, in the sense that we can approximate them to any given precision $\epsilon$. This is contrary to popular belief, as all dynamical properties are usually undecidable for Turing machines. The result is quite specific to one-tape Turing machines, as it is not true anymore for two-tape Turing machines by the results of Blondel et al., and uses the approach of crossing sequences introduced by Hennie.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.