# Enumeration of BPP machines

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?

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".
• If $M$ doesn’t halt after $p(|x|)$ steps, shouldn’t we output “no” instead of “yes”? – BlackHat18 Nov 30 '20 at 8:37
• Also, why is the set of probabilistic Turing machines $M$ enumerable? Can we map it to natural numbers like deterministic Turing machines? – BlackHat18 Nov 30 '20 at 8:38
• 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. – Yuval Filmus Nov 30 '20 at 8:48