-
J. D. Hamkins and A. Miasnikov, “The halting problem is decidable on a set of asymptotic probability one,” Notre Dame Journal of Formal Logic, vol. 47, iss. 4, p. 515–524, 2006.
[Bibtex]@ARTICLE{HamkinsMiasnikov2006:HaltingProblemDecidable, AUTHOR = {Hamkins, Joel David and Miasnikov, Alexei}, TITLE = {The halting problem is decidable on a set of asymptotic probability one}, JOURNAL = {Notre Dame Journal of Formal Logic}, VOLUME = {47}, YEAR = {2006}, NUMBER = {4}, PAGES = {515--524}, ISSN = {0029-4527}, CODEN = {NDJFAM}, MRCLASS = {03D10 (68Q05)}, MRNUMBER = {2272085 (2007m:03082)}, MRREVIEWER = {Maurice Margenstern}, DOI = {10.1305/ndjfl/1168352664}, URL = {http://jdh.hamkins.org/haltingproblemdecidable/}, eprint = {math/0504351}, archivePrefix = {arXiv}, primaryClass = {math.LO}, }
The halting problem for Turing machines is decidable on a set of asymptotic probability one. Specifically, there is a set B of Turing machine programs such that (i) B has asymptotic probability one, so that as the number of states n increases, the proportion of all n-state programs that are in B goes to one; (ii) B is polynomial time decidable; and (iii) the halting problem H intersect B is polynomial time decidable. The proof is sensitive to the particular computational model.