The undecidability of the Turing machine immortality problem

DOI10.2307/2269811MaRDI QIDQ5559248zbMATH OpenOpenAlexFDO

Authors 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

Cites work

• Computability of Recursive Functions
• 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

Cited in

(36)

• Complexity of certain decision problems about congruential languages
• The finite power property for context-free languages
• Some undecidability results concerning the property of preserving regularity
• Typability and type checking in System F are equivalent and undecidable
• Simple termination is difficult
• Decision problems for semi-Thue systems with a few rules
• On the presence of periodic configurations in Turing machines and in counter machines.
• Automatic graphs and D0L-sequences of finite graphs
• Undecidability of the speed positiveness problem in reversible and complete Turing machines
• On the domino problem of the Baumslag-Solitar groups
• The stability of the deterministic Skorokhod problem is undecidable
• Lower bounds for runtime complexity of term rewriting
• A decision procedure using discrete geometry
• Topological mixing notions on Turing machine dynamical systems
• A small minimal aperiodic reversible Turing machine
• Periodicity and Immortality in Reversible Computing
• The periodic domino problem revisited
• Diem-Grade Logischer Entscheidungsprobleme
• About the domino problem for subshifts on groups
• Simple termination is difficult
• The undecidability of the domino problem
• On the Undecidability of the Tiling Problem
• A survey of computational complexity results in systems and control
• Deciding stability and mortality of piecewise affine dynamical systems
• The stability of saturated linear dynamical systems is undecidable
• Quasi-periodic configurations and undecidable dynamics for tilings, infinite words and Turing machines
• On relations between properties in transitive Turing machines
• 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
• Some undecidable termination problems for semi-Thue systems
• Undecidability of semi-unification on a napkin
• Distortion element in the automorphism group of a full shift
• A categorical approach to reversible Turing machines and Brin-Thompson groups
• The immortality problem for Lag systems
• On deciding stability of multiclass queueing networks under buffer priority scheduling policies

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5559248)