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

  • J. D. Hamkins and A. Miasnikov, “The halting problem is decidable on a set of asymptotic probability one,” Notre Dame J. Formal Logic, vol. 47, iss. 4, pp. 515-524, 2006.  
    @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 J. Formal Logic},
    FJOURNAL = {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://dx.doi.org/10.1305/ndjfl/1168352664},
    eprint = {math/0504351},
    file = F,
    }

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.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>