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

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.
Fichier principal
Vignette du fichier
entropy.pdf (183.04 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

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
293 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More