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
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$– user94040Nov 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 probabilisticcomputable implies deterministiccomputable 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$– user94040Nov 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 6sided 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