Some undecidable problems about the trace-subshift associated to a Turing machine

Abstract : We consider three problems related to dynamics of one-tape Turing machines: Existence of blocking configurations, surjectivity in the trace, and entropy positiveness. In order to address them, a reversible two-counter machine is simulated by a reversible Turing machine on the right side of its tape. By completing the machine in different ways, we prove that none of the former problems is decidable. In particular, the problems about blocking configurations and entropy are shown to be undecidable for the class of reversible Turing machines.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no.2 (2), pp.267-284
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01349052
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 26 juillet 2016 - 17:24:03
Dernière modification le : mercredi 16 mai 2018 - 12:14:01

Fichier

2700-9828-1-PB.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-01349052, version 1

Collections

Citation

Anahí Gajardo, Nicolas Ollinger, Rodrigo Torres-Avilés. Some undecidable problems about the trace-subshift associated to a Turing machine. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no.2 (2), pp.267-284. 〈hal-01349052〉

Partager

Métriques

Consultations de la notice

95

Téléchargements de fichiers

241