The undecidability of the Turing machine immortality problem

DOI10.2307/2269811zbMath0173.01201OpenAlexW2161843469MaRDI QIDQ5559248

Philip K. Hooper

Publication date: 1966

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2269811

zbMATH Keywords

recursion theory, constructive mathematics

Related Items (33)

Automatic graphs and D0L-sequences of finite graphs ⋮ Complexity of certain decision problems about congruential languages ⋮ Simple termination is difficult ⋮ A small minimal aperiodic reversible Turing machine ⋮ Lower bounds for runtime complexity of term rewriting ⋮ Quasi-periodic configurations and undecidable dynamics for tilings, infinite words and Turing machines ⋮ Topological mixing notions on Turing machine dynamical systems ⋮ On relations between properties in transitive Turing machines ⋮ The periodic domino problem revisited ⋮ Positive First-order Logic on Words and Graphs ⋮ Constructive Many-one Reduction from the Halting Problem to Semi-unification (Extended Version) ⋮ Homotopy theory of monoid actions via group actions and an Elmendorf style theorem ⋮ The finite power property for context-free languages ⋮ About the Domino Problem for Subshifts on Groups ⋮ The immortality problem for Lag systems ⋮ The Undecidability of the Domino Problem ⋮ Some undecidable termination problems for semi-Thue systems ⋮ On the domino problem of the Baumslag-Solitar groups ⋮ A survey of computational complexity results in systems and control ⋮ Decision problems for semi-Thue systems with a few rules ⋮ Diem-Grade Logischer Entscheidungsprobleme ⋮ Deciding stability and mortality of piecewise affine dynamical systems ⋮ The stability of saturated linear dynamical systems is undecidable ⋮ On deciding stability of multiclass queueing networks under buffer priority scheduling policies ⋮ Periodicity and Immortality in Reversible Computing ⋮ Simple termination is difficult ⋮ On the Undecidability of the Tiling Problem ⋮ Undecidability of the speed positiveness problem in reversible and complete Turing machines ⋮ Some undecidability results concerning the property of preserving regularity ⋮ A decision procedure using discrete geometry ⋮ Typability and type checking in System F are equivalent and undecidable ⋮ The stability of the deterministic Skorokhod problem is undecidable ⋮ On the presence of periodic configurations in Turing machines and in counter machines.

Cites Work

• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Tag systems and lag systems
• Turing-machines and the Entscheidungsproblem
• Computability of Recursive Functions

This page was built for publication: The undecidability of the Turing machine immortality problem