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
External links referenced by this document: