On Immortal Configurations in Turing Machines - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2012

On Immortal Configurations in Turing Machines

Emmanuel Jeandel
Connectez-vous pour contacter l'auteur
Systèmes complexes, automates et pavages
CV

Résumé

We investigate the immortality problem for Turing machines and prove that there exists a Turing Machine that is immortal but halts on every recursive configuration. The result is obtained by combining a new proof of Hooper's theorem [11] with recent results on effective symbolic dynamics.

Domaines

Mathématique discrète [cs.DM]
Fichier principal
Vignette du fichier
turing.pdf (255.56 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Emmanuel Jeandel  : Connectez-vous pour contacter le contributeur

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00663457

Soumis le : vendredi 27 janvier 2012-10:57:37

Dernière modification le : vendredi 24 mars 2023-14:52:55

Archivage à long terme le : mercredi 14 décembre 2016-02:03:26

Télécharger pour visualiser

Dates et versions

lirmm-00663457 , version 1 (27-01-2012)

Identifiants

Citer

Emmanuel Jeandel. On Immortal Configurations in Turing Machines. CiE: Computability in Europe, 2012, Cambridge, United Kingdom. pp.334-343, ⟨10.1007/978-3-642-30870-3_34⟩. ⟨lirmm-00663457⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

CNRS ESCAPE LIRMM TDS-MACS MIPS UNIV-MONTPELLIER
378 Consultations
590 Téléchargements

Altmetric

Partager

More