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 &quot;yes&quot;.