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.
Type de document :
Communication dans un congrès
Ernst Mayr and Natacha Portier. STACS - Symposium on Theoretical Aspects of Computer Science, Mar 2014, Lyon, France. 25, pp.421-432, 2014, LIPCS. 〈10.4230/LIPIcs.STACS.2014.421〉
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00785232
Contributeur : Emmanuel Jeandel <>
Soumis le : mardi 5 février 2013 - 16:43:32
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25
Document(s) archivé(s) le : lundi 17 juin 2013 - 19:31:17

Fichiers

entropy.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Emmanuel Jeandel. Computability of the entropy of one-tape Turing Machines. Ernst Mayr and Natacha Portier. STACS - Symposium on Theoretical Aspects of Computer Science, Mar 2014, Lyon, France. 25, pp.421-432, 2014, LIPCS. 〈10.4230/LIPIcs.STACS.2014.421〉. 〈hal-00785232〉

Partager

Métriques

Consultations de la notice

350

Téléchargements de fichiers

309