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
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 25, 2016 at 18:35 | comment | added | Alex Mennen | 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 24, 2016 at 21:09 | review | First posts | |||
| Nov 24, 2016 at 21:25 | |||||
| Nov 24, 2016 at 21:04 | history | answered | none | CC BY-SA 3.0 |