The halting problem is decidable on a set of asymptotic probability one

DOI10.1305/ndjfl/1168352664zbMath1137.03024DBLPjournals/ndjfl/HamkinsM06arXivmath/0504351OpenAlexW1963569554WikidataQ56813206 ScholiaQ56813206MaRDI QIDQ2372684

Joel David Hamkins, Alexei G. Myasnikov

Publication date: 1 August 2007

Published in: Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0504351

zbMATH Keywords

asymptotic densityTuring machinehalting problemasymptotic probabilitypolynomial time decidability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Turing machines and related notions (03D10)

Related Items (20)

A generic relation on recursively enumerable sets ⋮ What Percentage of Programs Halt? ⋮ Generic complexity of Presburger arithmetic ⋮ Asymptotic density, immunity and randomness ⋮ On the generic undecidability of the halting problem for normalized Turing machines ⋮ On the strongly generic undecidability of the halting problem ⋮ Anytime Algorithms for Non-Ending Computations ⋮ Generic complexity of undecidable problems ⋮ Algorithmically finite groups. ⋮ Generic amplification of recursively enumerable sets ⋮ ON GENERIC COMPLEXITY OF THE QUADRATIC RESIDUOSITY PROBLEM ⋮ ON GENERIC COMPLEXITY OF THE VALIDITY PROBLEM FOR BOOLEAN FORMULAS ⋮ ON GENERIC COMPLEXITY OF THE DISCRETE LOGARITHM PROBLEM ⋮ ON GENERIC COMPLEXITY OF THE PROBLEM OF FINDING ROOTS IN GROUPS OF RESIDUES ⋮ Most programs stop quickly or never halt ⋮ On mathematical contributions of Paul E. Schupp ⋮ Exponentially generic subsets of groups ⋮ Generic Case Complexity and One-Way Functions ⋮ Generic case completeness ⋮ Generic undecidability of universal theories

This page was built for publication: The halting problem is decidable on a set of asymptotic probability one