1
$\begingroup$

Can we enumerate all probabilistic Turing machines (with bounded error), like we do for deterministic Turing machines (when using diagonalization arguments against deterministic Turing machines)? If not, does this mean we cannot diagonalize against BPP machines?

$\endgroup$
2
$\begingroup$

Yes. Enumerate over all pairs $(M,p)$ of probabilistic Turing machines $M$ and polynomials $p$. Interpret each such pair in the following way: on input $x$, run $M$ for $p(|x|)$ steps, and if it doesn't halt, output "yes".

$\endgroup$
  • $\begingroup$ If $M$ doesn’t halt after $p(|x|)$ steps, shouldn’t we output “no” instead of “yes”? $\endgroup$ – BlackHat18 Nov 30 '20 at 8:37
  • 1
    $\begingroup$ It doesn't matter what we output in that case. We could also toss a coin. $\endgroup$ – Yuval Filmus Nov 30 '20 at 8:37
  • $\begingroup$ Also, why is the set of probabilistic Turing machines $M$ enumerable? Can we map it to natural numbers like deterministic Turing machines? $\endgroup$ – BlackHat18 Nov 30 '20 at 8:38
  • $\begingroup$ It's exactly the same thing. If you can describe an object as a string, you can enumerate over all descriptions in order to enumerate over all objects. $\endgroup$ – Yuval Filmus Nov 30 '20 at 8:38
  • 1
    $\begingroup$ You might be able to cheat if you use arbitrary probabilities. In fact, in complexity theory we often tacitly assume that probabilities are of the form $a/2^b$ (or at the very least rational), though when describing algorithms we allow arbitrary probabilities. As long as all probabilities used are computable, the difference is pretty minor, and in particular, classes like BPP stay the same under all reasonable definitions. $\endgroup$ – Yuval Filmus Nov 30 '20 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.