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$?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
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$.
answered Nov 23, 2016 at 2:28
-
$\begingroup$ In other words are you saying $BPP$ is in computable hierarchy (since it is in polynomial hierarchy)? $\endgroup$– user94040Commented Nov 24, 2016 at 21:25
-
$\begingroup$ @AJ. Yes, every problem in BPP is computable. $\endgroup$ Commented 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$ Commented Nov 25, 2016 at 17:12
-
$\begingroup$ @GregKuperberg thank you for the clarification. would irrational probabilities make a difference? $\endgroup$– user94040Commented 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$ Commented Nov 28, 2016 at 7:26
$\begingroup$
$\endgroup$
1
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$ Commented Nov 25, 2016 at 18:35