# Computability of the entropy of one-tape Turing Machines

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.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [17 references]

https://hal.inria.fr/hal-00785232
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

entropy.pdf
Files produced by the author(s)

### 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⟩

### Metrics

Les métriques sont temporairement indisponibles