# Possible to construct a probabilistic halting problem solver?

I'm a CS undergrad so my math/CS knowledge is not that deep so please correct me if my premise is flawed or I have made some incorrect assumptions.

So I was thinking, much in the way that some primality testers are probabilistic(they give you yes or no but have a chance to be wrong). Would it be possible to build a probabilistic halting problem solver? One that reports within a certain degree of error, whether a problem halts or not?

• there exist halt-detection algorithms that succeed in giving the correct answer with some unknown probability and return "inconclusive" otherwise. these algorithms are studied eg in busy beaver research, automated thm proving, program termination analysis, & some other contexts. – vzn Feb 14 '14 at 5:46
• @vzn The sample algorithm running the input for $T$ steps also has the same properties. How are your algorithms better? Can you quantify it? – Yuval Filmus Feb 14 '14 at 6:12
• @YuvalFilmus it is probably theoretically impossible to compare these algorithms much; one way is mentioned in my answer on this question algorithm to solve halting problem... its an active area of research but also at the fringes of TCS without much widespread recognition of its significance/interconnection. the algorithms succeed in identifying some inputs that dont halt, which cannot be said of just running the TM on the inputs. intend to write up more detail on a blog at some pt (have various links). – vzn Feb 14 '14 at 16:47

For the second interpretation, we will have to work a bit harder. Suppose that your algorithm is guaranteed to work with an asymptotic success probability of $2/3$. That means that the fraction of inputs in $[1,N]$ for which it gives the correct answer is some $p_N \to 2/3$. Now suppose you're interested in a certain program $P$. It seems that under a reasonable encoding of programs, you would be able to come up with a long stretch $[M,10M]$ (say) of programs equivalent to $P$. By taking $M$ large enough, it should be the case that by taking the majority vote on the answer of a "probabilistic" algorithm on all of these equivalent programs, you will be able to ascertain whether $P$ halts or not. This rules out even this interpretation of a "probabilistic" algorithm.