Theoretical Computer Science
randomized-algorithms derandomization decidability halting-problem
Updated Sun, 22 May 2022 08:57:23 GMT

# Can the halting problem be solved probabilistically?

Let $$H$$ be the halting oracle, meaning that $$H$$ is a function on pairs of strings such that $$H(P,X) = 1$$ iff $$P$$ halts on $$X$$. A probabilistic program is a program that has (oracle) access to a random source. $$\def\pp{\mathbb{P}}$$

Can a probabilistic program solve the halting problem with probability more than $$1/2$$ for each input? That is, is there a probabilistic program $$G$$ such that $$\pp( \ G(P,X) = H(P,X) \ ) > 1/2$$ for every $$P,X$$? (Note that this in particular requires $$G$$ to halt with probability more than $$1/2$$.)

If $$G$$ always halts, and the random source is a fair coin, then this is impossible, because $$G$$ can only access the random source a certain number of times that is determined by the inputs (by weak Konig lemma), and so we can translate $$G$$ to an ordinary (non-probabilistic program) that solves the halting problem.

But my question is about the case where $$G$$ is not required to always halt, and the above argument fails. Also, in this case we can assume that the random source is a fair coin, since any other random source whose $$k$$-th output is a string drawn from a distribution computable from its previous outputs can be simulated using a fair coin with halting probability $$1$$.

Note that the strict bound of "$$> 1/2$$" is necessary, otherwise there is the obvious trivial solution. And note that I do not require the probability of success to be bounded away from $$1/2$$. The cases in this post do not cover my question, and I am unable to find any answer on the internet.

## Solution

It is well known that any language or function computable by a probabilistic algorithm is also computable deterministically. Here, we require that with probability $$>1/2$$, the algorithm outputs the correct answer (and therefore halts), but we allow the existence of infinite runs where the algorithm uses infinitely many random bits.

Indeed, by $$\sigma$$-additivity of the probabilistic measure, for any input $$x$$, there exists $$n$$ such that with probability $$>1/2$$, the algorithm computes the right answer within $$n$$ steps. Thus, we can find the answer deterministically as follows: for $$n=1,2,3,\dots$$, we simulate the algorithm for $$n$$ steps using all possible sequences of random bits (necessarily of length $$\le n$$) to count the probability that it halts with any particular answer; sooner or later, we find an $$n$$ and an answer thats output with probability $$>1/2$$ within $$n$$ steps, and then we declare the winner.

External links referenced by this document: