Skip to Main content Skip to Navigation
Conference papers

Computability of the entropy of one-tape Turing Machines

Emmanuel Jeandel 1
1 CARTE - Theoretical adverse computations, and safety
LORIA - FM - Department of Formal Methods , Inria Nancy - Grand Est
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
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 produced by the author(s)




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⟩



Record views


Files downloads