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
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 metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Emmanuel Jeandel Connect in order to contact the contributor
Submitted on : Tuesday, February 5, 2013 - 4:43:32 PM
Last modification on : Saturday, October 16, 2021 - 11:26:05 AM
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⟩



Les métriques sont temporairement indisponibles