On Immortal Configurations in Turing Machines - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2012

On Immortal Configurations in Turing Machines

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.
Fichier principal
Vignette du fichier
turing.pdf (255.56 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

Cite

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⟩
347 View
536 Download

Altmetric

Share

Gmail Facebook X LinkedIn More