Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

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
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00663457
Contributor : Emmanuel Jeandel Connect in order to contact the contributor
Submitted on : Friday, January 27, 2012 - 10:57:37 AM
Last modification on : Friday, October 22, 2021 - 3:07:35 PM
Long-term archiving on: : 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

326

Files downloads

470