<p><em>edit:</em> I just realized some of the things I wrote were total nonsense, sorry for that. Now I changed the proof and made the definition of probabilistic machine I am using more precise.</p>

<p>I don't know whether I get right your definition of probabilistic Turing machine: it is a machine with an additional tape on which an infinite incompressible string is written, and beside that it acts just like a deterministic machine? If we fix the incompressible string, the class we get doesn't seem to be interesting. </p>

<p>I think we can define a probabilistic Turing machine in several ways. I will use a definition that seems quite natural (and for which my proof works ;) Let's define a probabilistic machine like that: it gets an additional tape on which some infinite string is written, we say that this machine decides a language $L$ if for every $x \in L$ it halts and accepts with probability $>\frac{1}{2}$, when the probability is taken over those additional random strings, and for every $x \not \in L$ it halts and rejects with probability $>\frac{1}{2}$.</p>

<p>We will now show that if there exists such a probabilistic machine $P$ that solves the halting problem for the deterministic machines, we could use it to build a deterministic machine $H$ that solves the halting problem for the deterministic machines - and we know that such a machine cannot exist.</p>

<p>Assume such $P$ exists. We can construct a deterministic machine $M$ that takes as an input a probabilistic machine $R$ with some input $x$, which</p>

<ul>
<li>halts and accepts if and only if $R$ accepts $x$ (i.e. $R$ halts and accepts $x$ on more than half random strings).</li>
<li>halts and rejects if and only if $R$ rejects $x$ (i.e. $R$ halts and rejects $x$ on more than half random strings).</li>
<li>loops otherwise</li>
</ul>

<p>Basically, $M$ will for all $i \in 1, 2, ...$ simulate $R$ on input $x$ and on every string from ${{0,1}}^i$ as a prefix of the string on $R$'s random tape. Now:</p>

<ul>
<li>if for $>\frac{1}{2}$ prefixes of length $i$ $R$ halted and accepted without trying to read more than $i$ bits from the random tape, $M$ halts and accepts</li>
<li>if for $>\frac{1}{2}$ prefixes of length $i$ $R$ halted and rejected without trying to read more than $i$ bits from the random tape, $M$ halts and rejects</li>
<li>otherwise $M$ runs the simulation with $i := i+1$.</li>
</ul>

<p>We have to convince ourselves now, that if $R$ accepts (rejects) $x$ with probability $p >\frac{1}{2}$, then for some $i$ it will accept (reject) for $>\frac{1}{2}$ prefixes of length $i$ of the random string without trying to read more than $i$ bits from the random tape. It is technical, but quite easy - if we assume otherwise then the the probability of accepting (rejecting) approaches $p >\frac{1}{2}$ as $i$ goes to infinity, hence for some $i$ it will have to be $p >\frac{1}{2}$.</p>

<p>Now we just define our deterministic machine $H$ solving the halting problem (i.e. deciding whether a given deterministic machine $N$ accepts a given word $x$) a as $H(N,x) = M(P(N,x))$. Note that $M(P(N, x))$ always halts, because deciding a language by our probabilistic machines was defined in such a way that one of those two always occurs:</p>

<ul>
<li>the machine halts and accepts for more than half random strings</li>
<li>the machine halts and rejects for more than half random strings.</li>
</ul>

CC BY-SA 3.0
2017-09-22T03:39:46.560Z
The thing that I don't understand is how $M$ will ever know to run the simulation for $i := i+1$. You say that M should do this if $R$ halts and accepts or halts and rejects for > 1/2 of the inputs. But M cannot determine if $R$ halts on > 1/2 of the inputs -- because M cannot determine if $R$ will halt for even ONE input, because this itself is the halting problem! So you end up in a situation where $M$ has not yet gotten a result from 1/2 of the inputs, and is still waiting, but has no way of knowing if R just needs more time to halt and accept/reject on those, or if R is stuck in a loop!
Mike Battaglia
CC BY-SA 3.0
2017-09-22T04:08:35.213Z
Maybe it's a linguistic thing - do we assume that P halts on every input, and that it accepts/rejects correctly with probability > 50%? Or do we assume that it also only halts with probability > 50%? In other words, when this thing fails, is the failure mode that it simply gives the wrong output, or can it itself be stuck in an infinite loop as a failure mode?
Mike Battaglia
CC BY-SA 2.5
2010-10-28T08:31:26.727Z
Thanks for elaborating my "just enumerate" comment! ;) Two technical comments: At bullet point one, you mean $>2^{i-1}$? At the end, you mean $S(Q)$?
Raphael
CC BY-SA 2.5
2010-10-28T12:13:13.370Z
Note that if you do not require P to always halt, it is trivial to construct even a _deterministic_ Turing machine P which accepts if and only if the given deterministic Turing machine halts.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-28T14:39:17.610Z
What is your assumption?  You cannot negate a probabilistic Turing machine unless it is guaranteed to eventually halt.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-28T22:32:05.830Z
The halting probability is taken over the additional string AND input words, or what ?
Mohammad Alaggan
CC BY-SA 2.5
2010-10-28T23:56:51.650Z
@Tsuyoshi Ito - I think my proof before was seriously flawed to say the least (and definitively did not deserve the upvotes), I corrected it now.
Karolina Sołtys
CC BY-SA 2.5
2010-10-29T01:13:26.737Z
In the definition of a probabilistic Turing machine deciding a language L, you need an additional condition: if x∉L, it halts and rejects with probability > 1/2.  Other than that, I think that the proof is correct.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-29T07:56:00.950Z
Sure, I have forgotten to write that.
Karolina Sołtys
CC BY-SA 2.5
2010-10-29T15:35:16.867Z
@Mohammad ALAGGAN: No, that part is correct as is written: the probability is taken over only the additional string (specifying the results of the coin flips).  Because we are not assuming any probability distribution on the input string, the probability over the input string is not well-defined.  Even if a probability distribution on the input string is defined, the high probability of correct answer over the input string implies only that the algorithm is correct for most inputs, which is different from the usual requirement on an algorithm.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-28T07:59:55.113Z
2010-10-29T07:55:01.903Z
2010-10-29T07:55:01.903Z
Karolina Sołtys
<p>In general, if you have a probabilistic Turing machine $P$ solving some decision problem, you can always simulate it deterministically by running $P$ for every possible value of the randomness and outputting the majority answer of $P$. Therefore, no probabilistic Turing machine can solve an undecidable decision problem.</p>

<p>I think this was the meaning of Raphael's comment.</p>

CC BY-SA 2.5
2010-10-28T12:12:28.770Z
2010-10-28T12:12:28.770Z
Marc
<p>It depends on what you mean by a probabilistic algorithm determines some predicate.</p>

<p>There is a trivial probabilistic algorithm <i>P</i> such that, for a deterministic Turing machine <i>M</i>,</p>

<ul>
<li><i>P</i>(<i>M</i>) accepts with nonzero probability if <i>M</i> halts,</li>
<li><i>P</i>(<i>M</i>) never accepts if <i>M</i> does not halt, and</li>
<li><i>P</i>(<i>M</i>) halts with probability 1 for every <i>M</i>.</li>
</ul>

<p>Therefore, the probabilistic algorithm <i>P</i> solves the halting problem for deterministic Turing machines in this sense.  (Here “<i>M</i> halts” means “<i>M</i> halts on the empty input.”)</p>

<p>However, if you strengthen the requirement in any sensible way, it is unlikely that you can solve the halting problem for deterministic Turing machines anymore.  For example,</p>

<ul>
<li>If you require <i>P</i>(<i>M</i>) to halt <em>always</em> instead of merely <em>with probability 1</em>, then it is clear that <i>P</i> can be simulated by a deterministic algorithm.  (See <a href="http://en.wikipedia.org/wiki/Almost_surely#.22Almost_sure.22_versus_.22sure.22" rel="nofollow noreferrer">Wikipedia</a> for an explanation of the difference between “always” and “with probability 1.”)</li>
<li>If you make the error bounds strict by requiring <i>P</i>(<i>M</i>) to halt and give the right answer with probability strictly greater than 1/2 for every <i>M</i> (that is, you do not care if <i>P</i>(<i>M</i>) does not halt or halts and give the wrong answer in the rest of the cases), then <i>P</i> can be simulated by a deterministic algorithm by using the argument stated in <a href="https://cstheory.stackexchange.com/questions/2515/can-a-probabilistic-turing-machine-solve-the-halting-problem/2519#2519">Karolina Sołtys’s answer</a>.</li>
</ul>

<p>Therefore, a probabilistic algorithm cannot solve the halting problem for deterministic Turing machines in these senses.</p>

CC BY-SA 3.0
2017-09-22T04:15:51.693Z
If you allow for P(M) to fail by not halting, then I don't know how you can do a deterministic simulation. For instance, suppose you run your deterministic simulation on some set of length-N prefix strings, and after some length of time, < 50% of the prefixes have halted and given an answer. How do you know whether the remaining prefix strings simply need more time to return an answer, or if they are all stuck in an infinite loop as part of the failure condition? If the former, you continue to wait. If the latter, you terminate the current round and run again on all prefixes of length-N+1.
Mike Battaglia
CC BY-SA 3.0
2017-09-22T04:18:15.903Z
But this is impossible to determine, because it *is* the halting problem! We have no way of knowing whether the Turing machine will halt on those inputs or not.
Mike Battaglia
CC BY-SA 3.0
2017-09-27T13:02:23.623Z
@MikeBattaglia: I do not know why you are posting that as comments to my post. Of course, a Turing machine which halts on yes-instances and does not halt on no-instances cannot be simulated by a Turing machine which halts in acceptance on yes-instances and halts in rejection on no-instances in general. I have never claimed it can be. Anyway, I am much less active on this website now than 7 years ago, so excuse me if you reply and I do not respond.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-29T00:46:51.990Z
Forgive my ignorance, but what's the difference between halting ''always'' and halting ''with probability 1''?
Rob Simmons
CC BY-SA 2.5
2010-10-29T01:08:36.833Z
@Rob: I think that it is a tricky point.  Consider a simple probabilistic Turing machine which just tosses a coin repeatedly until the outcome is the heads.  This Turing machine halts except when all coin tosses result in the tails.  Therefore, it halts with probability 1, but it does not always halt.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-29T01:21:31.053Z
I found an [explanation of the difference between “always” and “with probability 1” in Wikipedia](http://en.wikipedia.org/wiki/Almost_surely#.22Almost_sure.22_versus_.22sure.22), and I added the same link in the answer.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-28T12:01:05.877Z
2010-10-29T01:19:58.043Z
2017-04-13T12:32:28.743Z
Tsuyoshi Ito
<p>If the Lebesgue measure of those oracles that compute a set $A\subseteq\mathbb N$ is positive, then $A$ is computable. This goes back to de Leeuw, Moore, Shannon, and Shapiro in 1956 and Sacks in 1963. For a discussion see Downey and Hirschfeldt's new book <em>Algorithmic randomness and complexity</em>. As other answers have mentioned, the idea is to take a majority vote. (While this can be done computably, there is no claim that the algorithm is efficient.)</p>

<p>de Leeuw, K., Moore, E. F., Shannon, C. E., and Shapiro, N. Computability
by probabilistic machines, Automata studies, pp. 183–212. Annals of
mathematics studies, no. 34. Princeton University Press, Princeton, N. J.,
1956.</p>

<p>G. Sacks, Degrees of Unsolvability, Princeton University Press, 1963.</p>

CC BY-SA 2.5
2010-11-01T17:20:46.223Z
2010-11-01T17:20:46.223Z
Bjørn Kjos-Hanssen
<p>A computer given an infinite stream of truly random bits is more powerful than a computer without one.  The question is: is it powerful enough to solve the halting problem?</p>

<p>That is, can a probabilistic computer determine whether or not a <strong>deterministic</strong> program halts?</p>

<p>Example of a probabilistic computer doing something a deterministic one can't: Consider a small program (less than a kilobyte in length) that outputs a string with Kolmogorov complexity greater than a gigabyte.  The <a href="http://en.wikipedia.org/wiki/Kolmogorov_complexity">Kolmogorov complexity</a> of a string is the length of the shortest deterministic program producing that string.  Thus, by definition, a deterministic program cannot produce a string whose complexity is greater than its own length.  However, if given an infinite stream of truly random bits, a small program is capable of achieving the task with 99.99999...% success by simply echoing out, say, 10 billion random bits and hoping the Kolmogorov complexity of those bits is high enough.  Hence, producing a string of superior Kolmogorov complexity is within the possibility horizon of the probabilistic program, but not possible at all for the deterministic program.</p>

<p>That said, I'm wondering if it is possible to use truly random bits to hacksaw at the halting problem.  For instance, an algorithm might randomly generate theorems and prove/disprove/discard them until it knows enough to prove/disprove that a given deterministic program halts.</p>

CC BY-SA 2.5
2010-10-28T07:14:21.350Z
@downvoter: This shouldn't have received a down-vote without a comment.
Dave Clarke
CC BY-SA 2.5
2010-10-28T07:19:03.620Z
What prevents a deterministic TM from enumerating all cases? Here, checking a guess is the problem, not guessing itself. Note also that you cannot really say you are strictly more powerful if you create the desired result only with a probability $p<1$.
Raphael
CC BY-SA 2.5
2010-10-28T12:02:14.347Z
"a deterministic program cannot produce a string whose complexity is greater than its own length." It is enough that some other deterministic machine outputs the same output. Note that deterministic TMs can simulate not only probabilistic ones, but even nondeterministic TMs (with arbitrary number of alternations).
Kaveh
CC BY-SA 2.5
2010-10-29T22:30:42.947Z
Yesterday I was about to say -- looking at Kaveh et al -- this was too basic a question for this site (same question for NTM is a basic result in every first theory course). Given that it took quite an effort to formalize "probabilistic TM", I am glad I did not.
Raphael
CC BY-SA 2.5
2010-11-01T17:52:47.997Z
And see the clarifying answers to my earlier related TCS question: http://cstheory.stackexchange.com/questions/1263/truly-random-number-generator-turing-computable
Joseph O'Rourke
<computability><randomness><turing-machines>
Can a probabilistic Turing machine solve the halting problem?
Joey Adams
# Can a probabilistic Turing machine solve the halting problem?

(Asked by: username_0 on 2010-10-28)

A computer given an infinite stream of truly random bits is more powerful than a computer without one. The question is: is it powerful enough to solve the halting problem?

That is, can a probabilistic computer determine whether or not a **deterministic** program halts?

Example of a probabilistic computer doing something a deterministic one can't: Consider a small program (less than a kilobyte in length) that outputs a string with Kolmogorov complexity greater than a gigabyte. The [Kolmogorov complexity](http://en.wikipedia.org/wiki/Kolmogorov_complexity) of a string is the length of the shortest deterministic program producing that string. Thus, by definition, a deterministic program cannot produce a string whose complexity is greater than its own length. However, if given an infinite stream of truly random bits, a small program is capable of achieving the task with 99.99999...% success by simply echoing out, say, 10 billion random bits and hoping the Kolmogorov complexity of those bits is high enough. Hence, producing a string of superior Kolmogorov complexity is within the possibility horizon of the probabilistic program, but not possible at all for the deterministic program.

That said, I'm wondering if it is possible to use truly random bits to hacksaw at the halting problem. For instance, an algorithm might randomly generate theorems and prove/disprove/discard them until it knows enough to prove/disprove that a given deterministic program halts.

**Tags:** computability, randomness, turing-machines
> **Comments:**
> **username_1**: @downvoter: This shouldn't have received a down-vote without a comment.  
> **username_2**: What prevents a deterministic TM from enumerating all cases? Here, checking a guess is the problem, not guessing itself. Note also that you cannot really say you are strictly more powerful if you create the desired result only with a probability $p<1$.  
> **username_3**: "a deterministic program cannot produce a string whose complexity is greater than its own length." It is enough that some other deterministic machine outputs the same output. Note that deterministic TMs can simulate not only probabilistic ones, but even nondeterministic TMs (with arbitrary number of alternations).  
> **username_2**: Yesterday I was about to say -- looking at Kaveh et al -- this was too basic a question for this site (same question for NTM is a basic result in every first theory course). Given that it took quite an effort to formalize "probabilistic TM", I am glad I did not.  
> **username_4**: And see the clarifying answers to my earlier related TCS question: http://cstheory.stackexchange.com/questions/1263/truly-random-number-generator-turing-computable  

---

## 4 answers

### Answer by username_5 on 2010-10-28. Score: 23

*edit:* I just realized some of the things I wrote were total nonsense, sorry for that. Now I changed the proof and made the definition of probabilistic machine I am using more precise.

I don't know whether I get right your definition of probabilistic Turing machine: it is a machine with an additional tape on which an infinite incompressible string is written, and beside that it acts just like a deterministic machine? If we fix the incompressible string, the class we get doesn't seem to be interesting.

I think we can define a probabilistic Turing machine in several ways. I will use a definition that seems quite natural (and for which my proof works ;) Let's define a probabilistic machine like that: it gets an additional tape on which some infinite string is written, we say that this machine decides a language $L$ if for every $x \in L$ it halts and accepts with probability $>\frac{1}{2}$, when the probability is taken over those additional random strings, and for every $x \not \in L$ it halts and rejects with probability $>\frac{1}{2}$.

We will now show that if there exists such a probabilistic machine $P$ that solves the halting problem for the deterministic machines, we could use it to build a deterministic machine $H$ that solves the halting problem for the deterministic machines - and we know that such a machine cannot exist.

Assume such $P$ exists. We can construct a deterministic machine $M$ that takes as an input a probabilistic machine $R$ with some input $x$, which

* halts and accepts if and only if $R$ accepts $x$ (i.e. $R$ halts and accepts $x$ on more than half random strings).
* halts and rejects if and only if $R$ rejects $x$ (i.e. $R$ halts and rejects $x$ on more than half random strings).
* loops otherwise

Basically, $M$ will for all $i \in 1, 2, ...$ simulate $R$ on input $x$ and on every string from ${{0,1}}^i$ as a prefix of the string on $R$'s random tape. Now:

* if for $>\frac{1}{2}$ prefixes of length $i$ $R$ halted and accepted without trying to read more than $i$ bits from the random tape, $M$ halts and accepts
* if for $>\frac{1}{2}$ prefixes of length $i$ $R$ halted and rejected without trying to read more than $i$ bits from the random tape, $M$ halts and rejects
* otherwise $M$ runs the simulation with $i := i+1$.

We have to convince ourselves now, that if $R$ accepts (rejects) $x$ with probability $p >\frac{1}{2}$, then for some $i$ it will accept (reject) for $>\frac{1}{2}$ prefixes of length $i$ of the random string without trying to read more than $i$ bits from the random tape. It is technical, but quite easy - if we assume otherwise then the the probability of accepting (rejecting) approaches $p >\frac{1}{2}$ as $i$ goes to infinity, hence for some $i$ it will have to be $p >\frac{1}{2}$.

Now we just define our deterministic machine $H$ solving the halting problem (i.e. deciding whether a given deterministic machine $N$ accepts a given word $x$) a as $H(N,x) = M(P(N,x))$. Note that $M(P(N, x))$ always halts, because deciding a language by our probabilistic machines was defined in such a way that one of those two always occurs:

* the machine halts and accepts for more than half random strings
* the machine halts and rejects for more than half random strings.

> **Comments:**
> **username_2**: Thanks for elaborating my "just enumerate" comment! ;) Two technical comments: At bullet point one, you mean $>2^{i-1}$? At the end, you mean $S(Q)$?  
> **username_7**: Note that if you do not require P to always halt, it is trivial to construct even a _deterministic_ Turing machine P which accepts if and only if the given deterministic Turing machine halts.  
> **username_7**: What is your assumption?  You cannot negate a probabilistic Turing machine unless it is guaranteed to eventually halt.  
> **username_8**: The halting probability is taken over the additional string AND input words, or what ?  
> **username_5**: @Tsuyoshi Ito - I think my proof before was seriously flawed to say the least (and definitively did not deserve the upvotes), I corrected it now.  
> **username_7**: In the definition of a probabilistic Turing machine deciding a language L, you need an additional condition: if x∉L, it halts and rejects with probability > 1/2.  Other than that, I think that the proof is correct.  
> **username_5**: Sure, I have forgotten to write that.  
> **username_7**: @Mohammad ALAGGAN: No, that part is correct as is written: the probability is taken over only the additional string (specifying the results of the coin flips).  Because we are not assuming any probability distribution on the input string, the probability over the input string is not well-defined.  Even if a probability distribution on the input string is defined, the high probability of correct answer over the input string implies only that the algorithm is correct for most inputs, which is different from the usual requirement on an algorithm.  
> **username_6**: The thing that I don't understand is how $M$ will ever know to run the simulation for $i := i+1$. You say that M should do this if $R$ halts and accepts or halts and rejects for > 1/2 of the inputs. But M cannot determine if $R$ halts on > 1/2 of the inputs -- because M cannot determine if $R$ will halt for even ONE input, because this itself is the halting problem! So you end up in a situation where $M$ has not yet gotten a result from 1/2 of the inputs, and is still waiting, but has no way of knowing if R just needs more time to halt and accept/reject on those, or if R is stuck in a loop!  
> **username_6**: Maybe it's a linguistic thing - do we assume that P halts on every input, and that it accepts/rejects correctly with probability > 50%? Or do we assume that it also only halts with probability > 50%? In other words, when this thing fails, is the failure mode that it simply gives the wrong output, or can it itself be stuck in an infinite loop as a failure mode?  

---

### Answer by username_7 on 2010-10-28. Score: 15

It depends on what you mean by a probabilistic algorithm determines some predicate.

There is a trivial probabilistic algorithm *P* such that, for a deterministic Turing machine *M*,

* *P*(*M*) accepts with nonzero probability if *M* halts,
* *P*(*M*) never accepts if *M* does not halt, and
* *P*(*M*) halts with probability 1 for every *M*.

Therefore, the probabilistic algorithm *P* solves the halting problem for deterministic Turing machines in this sense. (Here “*M* halts” means “*M* halts on the empty input.”)

However, if you strengthen the requirement in any sensible way, it is unlikely that you can solve the halting problem for deterministic Turing machines anymore. For example,

* If you require *P*(*M*) to halt *always* instead of merely *with probability 1*, then it is clear that *P* can be simulated by a deterministic algorithm. (See [Wikipedia](http://en.wikipedia.org/wiki/Almost_surely#.22Almost_sure.22_versus_.22sure.22) for an explanation of the difference between “always” and “with probability 1.”)
* If you make the error bounds strict by requiring *P*(*M*) to halt and give the right answer with probability strictly greater than 1/2 for every *M* (that is, you do not care if *P*(*M*) does not halt or halts and give the wrong answer in the rest of the cases), then *P* can be simulated by a deterministic algorithm by using the argument stated in [Karolina Sołtys’s answer](https://cstheory.stackexchange.com/questions/2515/can-a-probabilistic-turing-machine-solve-the-halting-problem/2519#2519).

Therefore, a probabilistic algorithm cannot solve the halting problem for deterministic Turing machines in these senses.

> **Comments:**
> **username_10**: Forgive my ignorance, but what's the difference between halting ''always'' and halting ''with probability 1''?  
> **username_7**: @Rob: I think that it is a tricky point.  Consider a simple probabilistic Turing machine which just tosses a coin repeatedly until the outcome is the heads.  This Turing machine halts except when all coin tosses result in the tails.  Therefore, it halts with probability 1, but it does not always halt.  
> **username_7**: I found an [explanation of the difference between “always” and “with probability 1” in Wikipedia](http://en.wikipedia.org/wiki/Almost_surely#.22Almost_sure.22_versus_.22sure.22), and I added the same link in the answer.  
> **username_6**: If you allow for P(M) to fail by not halting, then I don't know how you can do a deterministic simulation. For instance, suppose you run your deterministic simulation on some set of length-N prefix strings, and after some length of time, < 50% of the prefixes have halted and given an answer. How do you know whether the remaining prefix strings simply need more time to return an answer, or if they are all stuck in an infinite loop as part of the failure condition? If the former, you continue to wait. If the latter, you terminate the current round and run again on all prefixes of length-N+1.  
> **username_6**: But this is impossible to determine, because it *is* the halting problem! We have no way of knowing whether the Turing machine will halt on those inputs or not.  
> **username_7**: @MikeBattaglia: I do not know why you are posting that as comments to my post. Of course, a Turing machine which halts on yes-instances and does not halt on no-instances cannot be simulated by a Turing machine which halts in acceptance on yes-instances and halts in rejection on no-instances in general. I have never claimed it can be. Anyway, I am much less active on this website now than 7 years ago, so excuse me if you reply and I do not respond.  

---

### Answer by username_9 on 2010-10-28. Score: 12

In general, if you have a probabilistic Turing machine $P$ solving some decision problem, you can always simulate it deterministically by running $P$ for every possible value of the randomness and outputting the majority answer of $P$. Therefore, no probabilistic Turing machine can solve an undecidable decision problem.

I think this was the meaning of Raphael's comment.


---

### Answer by username_11 on 2010-11-01. Score: 9

If the Lebesgue measure of those oracles that compute a set $A\subseteq\mathbb N$ is positive, then $A$ is computable. This goes back to de Leeuw, Moore, Shannon, and Shapiro in 1956 and Sacks in 1963. For a discussion see Downey and Hirschfeldt's new book *Algorithmic randomness and complexity*. As other answers have mentioned, the idea is to take a majority vote. (While this can be done computably, there is no claim that the algorithm is efficient.)

de Leeuw, K., Moore, E. F., Shannon, C. E., and Shapiro, N. Computability
by probabilistic machines, Automata studies, pp. 183–212. Annals of
mathematics studies, no. 34. Princeton University Press, Princeton, N. J.,
1956.

G. Sacks, Degrees of Unsolvability, Princeton University Press, 1963.


---

