Computability of the entropy of one-tape Turing Machines - Archive ouverte HAL Access content directly
Conference Papers Year : 2014

Computability of the entropy of one-tape Turing Machines

(1)
1
Emmanuel Jeandel

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.

Dates and versions

hal-00785232 , version 1 (05-02-2013)

Identifiers

• HAL Id : hal-00785232 , version 1
• ARXIV :
• DOI :

Cite

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⟩

369 View