HackerPapers

arXiv:math/0504351math.LO

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

Joel David Hamkins, Alexei Miasnikov

Abstract

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.

arXiv comments
10 pages
Journal reference
DOI
Subjects
math.LOLogic

On Hacker News

Linked by 3 identifiable commenters in 4 comments across 4 threads, from Aug 2018 to Jan 2024. Found in 2 HN submissions from Sep 2016 to Jun 2021. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments4 threads

  1. Learning Universal Predictors 1 comment

    • I see your pathological proof of existence and raise you an asymptotic probability of one: “The halting problem for Turing machines is perhaps the canonical undecidable set. Nevertheless, we prove that there is an algorithm deciding almost all instances of it.”…

      XcelerateView on HNParent context

  2. The halting problem is decidable on a set of asymptotic probability one (2005) 1 comment

    • (2005) and I think the URL should be https://arxiv.org/abs/math/0504351 (that is, you forgot the path component "math")

      schoenView on HNParent context

  3. Mathematical Simplicity May Drive Evolution's Speed 1 comment

    • Looks like the paper is a lot older than I thought it was: https://arxiv.org/abs/math/0504351 My code isn't public at the moment. It's written in Julia and rather messy so I'd have to clean it up a bit, but I wouldn't be opposed to putting it on Github. I really like your…

      XcelerateView on HNParent context

  4. Kolmogorov Complexity and Our Search for Meaning 1 comment

    • Well, obviously, the shortest program that outputs "0" is "0". And the shortest program that outputs "1" is "1". We're only interested in the general case, not specific cases. Just wanted to note that we have techniques for termination analysis that cover entire classes of…

      antidesitterView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.