Is there an algorithm that probably solves the Halting problem?

Question

Such an algorithm takes as input any program and returns a probability that it halts.

In the limit of many programs, it must answer on average in the correct proportion. But im interested in other interesting conditions for a succesfull algorithm

Answer 1

There are several significant ambiguities in your question. The way the machines are encoded matters for this, as does the model of computation. Also, do you mean that the machine always halts, or that it halts for zero input? I will make reasonable assumptions to resolve these ambiguities, if that does not do it for you you will need to clarify your question.

Suppose the computational model is the single one way infinite tape binary alphabet Turing Machine model. Suppose the initial input is zero; a machine running on nonzero input is equivalent to some easily identified machine with more states running on zero input, so this is a reasonable assumption. Finally, list the machines such that $k<m$ implies machine $k$ has no more states than machine $m$; this is not overly restrictive, as one would expect any reasonable encoding to be close enough to this for the following to work.

It has recently been proven that a polynomial time program can decide all but a diminishing proportion of TM's, see http://arxiv.org/abs/math/0504351. Then you could just run this program and guess on machines it can't decide (or say they all halt or all don't, or whatever). Since the possible mistakes are a diminishing proportion of inputs, this is the algorithm you are looking for.

The result this answer relies on applies with additional tapes and characters in the alphabet. I do not think it is yet known to apply in the case of the two way infinite tape. However, it seems to me that this is likely the case. The paper I cited actually states this as an open question.