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

DOI10.1305/ndjfl/1168352664zbMath1137.03024arXivmath/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

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