Computability of the entropy of one-tape Turing Machines

Emmanuel Jeandel 1
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
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.
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-00785232
Contributor : Emmanuel Jeandel <>
Submitted on : Tuesday, February 5, 2013 - 4:43:32 PM
Last modification on : Tuesday, December 18, 2018 - 4:48:02 PM
Long-term archiving on : Monday, June 17, 2013 - 7:31:17 PM

Files

entropy.pdf
Files produced by the author(s)

Identifiers

Citation

Emmanuel Jeandel. Computability of the entropy of one-tape Turing Machines. STACS - Symposium on Theoretical Aspects of Computer Science, Mar 2014, Lyon, France. pp.421-432, ⟨10.4230/LIPIcs.STACS.2014.421⟩. ⟨hal-00785232⟩

Share

Metrics

Record views

559

Files downloads

342