On Immortal Configurations in Turing Machines

Emmanuel Jeandel 1, *
* Corresponding author
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [18 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00663457
Contributor : Emmanuel Jeandel <>
Submitted on : Friday, January 27, 2012 - 10:57:37 AM
Last modification on : Thursday, May 24, 2018 - 3:59:23 PM
Document(s) archivé(s) le : Wednesday, December 14, 2016 - 2:03:26 AM

File

turing.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

543

Files downloads

342