On the generic undecidability of the halting problem for normalized Turing machines

DOI10.1007/S00224-016-9698-9MaRDI QIDQ2398210zbMATH OpenOpenAlexFDO

Authors Alexander Rybalov

Publication date 15 August 2017

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-016-9698-9

zbMATH Keywords

generic complexityhalting problem

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Undecidability and degrees of sets of sentences (03D35)

Recommendations

• On the strongly generic undecidability of the halting problem
• Generic algorithms for halting problem and optimal machines revisited
• The halting problem is decidable on a set of asymptotic probability one
• Generic complexity of undecidable problems
• scientific article; zbMATH DE number 1114344

Cites work

• A Theory of Program Size Formally Identical to Information Theory
• Generic-case complexity, decision problems in group theory, and random walks.
• Most programs stop quickly or never halt
• On the strongly generic undecidability of the halting problem
• The halting problem is decidable on a set of asymptotic probability one

Cited in

(7)

• Bounding lemmata for non-deterministic halting times of transfinite Turing machines
• Generic Complexity of Undecidable Problems
• The laterality problem for non-erasing Turing machines on \lbrace 0,1\rbrace is completely solved
• Non-erasing turing machines: A new frontier between a decidable halting problem and universality
• Logical Approaches to Computational Barriers
• Decidability of the halting problem for Matiyasevich deterministic machines
• On the strongly generic undecidability of the halting problem

This page was built for publication: On the generic undecidability of the halting problem for normalized Turing machines

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