<p>It is well known that any language or function computable by a probabilistic algorithm is also computable deterministically. Here, we require that with probability <span class="math-container">$&gt;1/2$</span>, 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.</p>
<p>Indeed, by <span class="math-container">$\sigma$</span>-additivity of the probabilistic measure, for any input <span class="math-container">$x$</span>, there exists <span class="math-container">$n$</span> such that with probability <span class="math-container">$&gt;1/2$</span>, the algorithm computes the right answer within <span class="math-container">$n$</span> steps. Thus, we can find the answer deterministically as follows: for <span class="math-container">$n=1,2,3,\dots$</span>, we simulate the algorithm for <span class="math-container">$n$</span> steps using all possible sequences of random bits (necessarily of length <span class="math-container">$\le n$</span>) to count the probability that it halts with any particular answer; sooner or later, we find an <span class="math-container">$n$</span> and an answer that’s output with probability <span class="math-container">$&gt;1/2$</span> within <span class="math-container">$n$</span> steps, and then we declare the winner.</p>

CC BY-SA 4.0
2020-10-20T11:46:05.063Z
2020-10-20T12:15:02.673Z
2020-10-20T12:15:02.673Z
Emil Jeřábek
<p>Let <span class="math-container">$H$</span> be the halting oracle, meaning that <span class="math-container">$H$</span> is a function on pairs of strings such that <span class="math-container">$H(P,X) = 1$</span> iff <span class="math-container">$P$</span> halts on <span class="math-container">$X$</span>. A <strong>probabilistic program</strong> is a program that has (oracle) access to a random source.
<span class="math-container">$
\def\pp{\mathbb{P}}
$</span></p>
<p>Can a probabilistic program solve the halting problem with probability more than <span class="math-container">$1/2$</span> for each input? That is, is there a probabilistic program <span class="math-container">$G$</span> such that <span class="math-container">$\pp( \ G(P,X) = H(P,X) \ ) &gt; 1/2$</span> for every <span class="math-container">$P,X$</span>? (Note that this in particular requires <span class="math-container">$G$</span> to halt with probability more than <span class="math-container">$1/2$</span>.)</p>
<p>If <span class="math-container">$G$</span> always halts, and the random source is a fair coin, then this is impossible, because <span class="math-container">$G$</span> 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 <span class="math-container">$G$</span> to an ordinary (non-probabilistic program) that solves the halting problem.</p>
<p>But my question is about the case where <span class="math-container">$G$</span> 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 <span class="math-container">$k$</span>-th output is a string drawn from a distribution computable from its previous outputs can be simulated using a fair coin with halting probability <span class="math-container">$1$</span>.</p>
<p>Note that the strict bound of &quot;<span class="math-container">$&gt; 1/2$</span>&quot; 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 <span class="math-container">$1/2$</span>. The cases in <a href="https://cstheory.stackexchange.com/a/2521">this post</a> do not cover my question, and I am unable to find any answer on the internet.</p>

CC BY-SA 4.0
2020-10-19T08:25:35.807Z
By the way, I am sure the answer is "no", but I cannot prove it.
user21820
CC BY-SA 4.0
2020-10-19T09:48:50.727Z
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.
Denis
CC BY-SA 4.0
2020-10-19T09:49:20.933Z
@Denis: That's exactly what I said in my post, in paragraphs 3 and 4.
user21820
CC BY-SA 4.0
2020-10-19T09:54:28.183Z
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.
Denis
CC BY-SA 4.0
2020-10-19T10:03:45.757Z
@Denis: Paragraph 3 says that if we demand that $G$ is total and the random source is a fair coin, then it is impossible. Paragraph 4 says that I do not require $G$ to be total, and so the argument in the previous paragraph does not apply, and moreover in this case we can assume that the random source is a fair coin, since it does not affect the probability of $G$ halting. I never claimed anything about a program that halts with probability 1 and yet solves the halting problem with probability $>1/2$. But can you construct such a program? It would be far stronger than what I think impossible.
user21820
CC BY-SA 4.0
2020-10-19T10:14:01.247Z
I don't have such a program, my remark was just to emphasize the difference between "total" and "total with probability 1", I was not contradicting what you wrote, just trying to precise it.
Denis
CC BY-SA 4.0
2020-10-19T10:23:29.357Z
Okay. Anyway I don't see anything imprecise in my post at all (as explained above), since I used the 100% precise phrase "always halts". I did originally want to know whether there was a program that almost always halts and does better than a coin flip, but I realized I could not even find one even when removing the condition "almost always halts". Hence my question.
user21820
CC BY-SA 4.0
2020-10-19T19:31:17.250Z
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.
daniello
CC BY-SA 4.0
2020-10-19T19:48:33.837Z
@daniello: You're right. I'm not sure why I didn't realize that. If you post that as an answer, I will accept it.
user21820
CC BY-SA 4.0
2020-10-20T10:34:36.963Z
How does https://cstheory.stackexchange.com/a/2519 not answer the question?
Emil Jeřábek
CC BY-SA 4.0
2020-10-20T12:15:25.607Z
@EmilJeřábek: I didn't realize it, perhaps because the original question I had in mind allowed random sources that were not just uniformly random bits, then after I made the reduction I forgot to check whether that post applied or not...
user21820
<randomized-algorithms><derandomization><decidability><halting-problem>
Can the halting problem be solved probabilistically?
user21820
# Can the halting problem be solved probabilistically?

(Asked by: username_0 on 2020-10-19)

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](https://cstheory.stackexchange.com/a/2521) do not cover my question, and I am unable to find any answer on the internet.

**Tags:** randomized-algorithms, derandomization, decidability, halting-problem
> **Comments:**
> **username_0**: By the way, I am sure the answer is "no", but I cannot prove it.  
> **username_1**: 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.  
> **username_0**: @Denis: That's exactly what I said in my post, in paragraphs 3 and 4.  
> **username_1**: 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.  
> **username_0**: @Denis: Paragraph 3 says that if we demand that $G$ is total and the random source is a fair coin, then it is impossible. Paragraph 4 says that I do not require $G$ to be total, and so the argument in the previous paragraph does not apply, and moreover in this case we can assume that the random source is a fair coin, since it does not affect the probability of $G$ halting. I never claimed anything about a program that halts with probability 1 and yet solves the halting problem with probability $>1/2$. But can you construct such a program? It would be far stronger than what I think impossible.  
> **username_1**: I don't have such a program, my remark was just to emphasize the difference between "total" and "total with probability 1", I was not contradicting what you wrote, just trying to precise it.  
> **username_0**: Okay. Anyway I don't see anything imprecise in my post at all (as explained above), since I used the 100% precise phrase "always halts". I did originally want to know whether there was a program that almost always halts and does better than a coin flip, but I realized I could not even find one even when removing the condition "almost always halts". Hence my question.  
> **username_2**: 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.  
> **username_0**: @daniello: You're right. I'm not sure why I didn't realize that. If you post that as an answer, I will accept it.  
> **username_3**: How does https://cstheory.stackexchange.com/a/2519 not answer the question?  
> **username_0**: @EmilJeřábek: I didn't realize it, perhaps because the original question I had in mind allowed random sources that were not just uniformly random bits, then after I made the reduction I forgot to check whether that post applied or not...  

---

## 1 answers

### Answer by username_3 on 2020-10-20. Score: 8 | Accepted answer

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.


---

