# Is there a noncomputable set which can be described by a probabilistic Turing machine with bounded error?

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$?

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$.

• In other words are you saying $BPP$ is in computable hierarchy (since it is in polynomial hierarchy)?
– user94040
Nov 24, 2016 at 21:25
• @AJ. Yes, every problem in BPP is computable. Nov 25, 2016 at 5:04
• 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. Nov 25, 2016 at 17:12
• @GregKuperberg thank you for the clarification. would irrational probabilities make a difference?
– user94040
Nov 26, 2016 at 21:36
• 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. 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.

• 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$. Nov 25, 2016 at 18:35