Is it possible to make an algorithm that could predict the likelihood that a program will halt? 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. 
 A: Here is one way of interpreting your question. In my joint paper:


*

*Joel David Hamkins and Alexei Miasnikov, The halting problem is decidable on a set of asymptotic probability one, Notre Dame J. Formal Logic 47 (2006), no. 4, 515--524. blog post,


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%. 
