3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ By the way, I am sure the answer is "no", but I cannot prove it. $\endgroup$ – user21820 Oct 19 '20 at 8:25
  • $\begingroup$ Your Konig argument does not apply if you only assume your program halts with probability 1: an infinite branch of the tree can have probability 0 to happen. $\endgroup$ – Denis Oct 19 '20 at 9:48
  • $\begingroup$ @Denis: That's exactly what I said in my post, in paragraphs 3 and 4. $\endgroup$ – user21820 Oct 19 '20 at 9:49
  • $\begingroup$ It's not what I understand from these paragraphs. You say that you can go from any random source to fair coin with halting probaility 1, but this "halting probability 1" is already outside of what you consider is a program that always halt, according to the previous paragraph. Anyway my comment was just a remark, saying that your Konig argument does not rule out a program with halting probability 1, giving a good answer with proba >1/2. $\endgroup$ – Denis Oct 19 '20 at 9:54
  • 1
    $\begingroup$ I think one can still reduce regular halting problem to this; cant you just simulate the TM for “all random seeds” in parallell and you stop and give an output when one of the options reaches probability > 1/2. This does assume that the randomness is a stream of independent fair coins. $\endgroup$ – daniello Oct 19 '20 at 19:31
6
$\begingroup$

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 that’s output with probability $>1/2$ within $n$ steps, and then we declare the winner.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.