18
$\begingroup$

Today I began to read about computability theory. I do not even have an elementary understanding of the topic but it certainly got me thinking. I know there is there is no 'one-for-all' algorithm that solves the halting problem but I wonder if it is possible for there to be an algorithm that determines the likelihood that a program would halt.

The reason I asked this question because I'm writing an essay about a problem I would like to solve and I thought this might be an interesting "solution" to the halting problem.

And yes I know the halting problem is undecidable.

Improve this question
$\endgroup$
8

1 Answer 1

Reset to default
27
$\begingroup$

Here is one way of interpreting your question. In my joint paper:

the main theorem is that for some of the standard models of computation, the halting problem is decidable with probability one. Specifically, we prove that for the usual one-way-infinite Turing machine model, there is a set $A$ of Turing machine programs, such that:

  • Almost every program is in $A$, in the sense that the proportion of all $n$-state programs in $A$ goes to $1$ as $n$ goes to infinity;
  • it is decidable whether a given program is in $A$; and
  • the halting problem is decidable for programs in $A$.

So this is a sense in which the halting problem is decidable with probability one.

The argument is sensitive, however, to the computational model, and for some other models of computation, the best currently known is that we can decide the halting problem on a set of probability $\frac 1{e^2}$, which is about 13.5%.

Improve this answer
$\endgroup$
4
  • $\begingroup$ How does this relate to mathoverflow.net/questions/4454 , which asks for the probability that a random grammatical sentence is proveable in PA? Normally, I think of halting and provability as pretty similar, but the answers seem to be very different. $\endgroup$
    – David E Speyer
    Commented Dec 1, 2015 at 14:04
  • 3
    $\begingroup$ Since the probability of halting depends on the computational model, one shouldn't think of it as a robust concept of computability, and already different models of computation lead to different probabilities. Nevertheless, your idea over there has an analogue in computability: fixing a specific line of the TM program. But for TMs, doing so makes a set of measure zero, since otherwise the line could have transitioned to any of a large number of states. In your context, this is like having an infinite language, in which case your calculation would no longer work. $\endgroup$
    – Joel David Hamkins
    Commented Dec 1, 2015 at 15:58
  • $\begingroup$ Sorry, I meant, "robust concept of computational probability". The model of computability is completely standard and robust, Turing complete, etc. But when a concept depends on the computational model, as the probabilities do here, then we are hesitant to say that it is actually a concept relating to computability as such. $\endgroup$
    – Joel David Hamkins
    Commented Dec 1, 2015 at 22:21
  • $\begingroup$ A quick note: it is also known that there are "models of computation" (in the sense of enumerations of partial algorithms) in which the halting problem cannot be decided with (asymptotic) probability 1; that is, the probability of correct convergence must be less than 1 or undefined. However, I'm not sure if this is known for any natural models that weren't simply constructed to prove this theorem. $\endgroup$
    – Eric Astor
    Commented Dec 6, 2015 at 4:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .