Como consecuencia, una máquina de Turing probabilística puede (a diferencia de una máquina de Turing) tener un resultado estocástico: Dada una entrada y un programa para la máquina, puede ejecutar el programa en tiempos variables de ejecución o puede no parar; más aún, puede aceptar una entrada en una ejecución y no aceptarla en la siguiente.
Y a esas formas de terminar corresponden diferentes clases de complejidad que incluyen RP, Co-RP.
Al restringirse la máquina a solo usar espacio logarítmico en lugar de tiempo polinómico, se definen las clases análogas RL, Co-RL, BPL, y ZPL.
Al incluir ambas restricciones se obtienen las clases RLP, Co-RPL, BPLP y ZPLP.
Los computadores cuánticos son otro modelo de cálculo que es inherentemente probabilístico.