Does there exist any noncomputable set $A$ and probabilistic Turing machine $M$ such that $\forall n\in A$ $M(n)$ halts and outputs $1$ with probability at least $2/3$, and $\forall n\in\mathbb{N}\setminus A$ $M(n)$ halts and outputs $0$ with probability at least $2/3$? What if you only require that $M(n)$ is correct with probability greater than $1/2$?


2 Answers 2


Every such decision problem is computable, even in the harder version of the problem, assuming that the transition probabilities are, say, fixed rational numbers. A deterministic algorithm can calculate the probability distribution on the set of states of this stochastic TM after each $t$ time steps, and then step through $t$ until the probability of halt at either yes or no exceeds $1/2$.

  • $\begingroup$ In other words are you saying $BPP$ is in computable hierarchy (since it is in polynomial hierarchy)? $\endgroup$
    – user94040
    Nov 24, 2016 at 21:25
  • $\begingroup$ @AJ. Yes, every problem in BPP is computable. $\endgroup$ Nov 25, 2016 at 5:04
  • 2
    $\begingroup$ Every problem in BPP is indeed in the polynomial hierarchy, and therefore in the computable hierarchy, but that is not what I'm saying. Algorithms in BPP are a priori time bounded, which can be interpreted as a second reason that everything BPP is computable. By contrast a general recursive algorithm is not a priori time bounded; it only finds its own reasons to eventually stop. Thus, the result that probabilistic-computable implies deterministic-computable does not reduce to a question about BPP. $\endgroup$ Nov 25, 2016 at 17:12
  • $\begingroup$ @GregKuperberg thank you for the clarification. would irrational probabilities make a difference? $\endgroup$
    – user94040
    Nov 26, 2016 at 21:36
  • $\begingroup$ For the question as stated, they would only make a difference for an unfair reason. If a transition probability is itself an uncomputable real number, then its bit expansion can be extracted by a Turing machine. On the other hand, if there are finitely many transition probabilities and they are all computable, then a slightly more complicated argument shows that everything that the TM can do is still computable in the usual sense. $\endgroup$ Nov 28, 2016 at 7:26

Construct $A$ as follows. Roll a 6-sided die infinitely many times, giving output $r_1,r_2\dots$.

Now for odd $k$, say $k\in A$ iff $r_k=6$. For even $k$, say $k\in A$ iff $r_k<6$. So $k\in A$ with probability 1/6 if $k$ is odd, and $5/6$ if $k$ is even. $A$ is obviously incomputable.

Turing machine $M$ on input $k$ simply answers 1 if $k$ is even, $0$ otherwise. So it is correct 5/6 of the time.

  • $\begingroup$ That doesn't work. Let $k$ be even with $k\notin A$. Then $M$ will guess that $k\in A$ and be wrong with probability 1. I wanted $M$ to be correct with probability greater than $1/2$ on every fixed $k$, not just for it to be right about most $k$. $\endgroup$ Nov 25, 2016 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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