Timeline for Is there a noncomputable set which can be described by a probabilistic Turing machine with bounded error?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 28, 2016 at 7:26 | comment | added | Greg Kuperberg | 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 26, 2016 at 21:36 | comment | added | user94040 | @GregKuperberg thank you for the clarification. would irrational probabilities make a difference? | |
| Nov 25, 2016 at 17:12 | comment | added | Greg Kuperberg | 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 5:04 | comment | added | Noah Schweber | @AJ. Yes, every problem in BPP is computable. | |
| Nov 24, 2016 at 21:25 | comment | added | user94040 | In other words are you saying $BPP$ is in computable hierarchy (since it is in polynomial hierarchy)? | |
| Nov 23, 2016 at 2:32 | vote | accept | Alex Mennen | ||
| Nov 23, 2016 at 2:28 | history | answered | Greg Kuperberg | CC BY-SA 3.0 |