Máquina de Turing probabilística
De Wikipedia, la enciclopedia libre
En Teoría de la complejidad computacional, se utilizan Máquinas de Turing probabilísticas para definir diferentes clases de complejidad.
Una Máquina de Turing probabilística es una Máquina de Turing, en concreto de la forma no determinista, que selecciona aleatoriamente entre las transiciones disponibles en cada punto con idéntica probabilidad para cada alternativa.
Alternativamente, se pude definir también como una máquina de Turing determinista con una instrucción adicional “escribir” donde el valor de la escritura está uniformemente distribuido en el alfabeto de la máquina.
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.
Se desprende que la aceptación de una cadena de entrada en una máquina de Turing probabilística puede ser definida de varias formas. Y a esas formas de terminar corresponden diferentes clases de complejidad que incluyen RP, Co-RP. BPP y ZPP. Al restringirse la máquina a sólo 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 yZPLP.
Los computadores cuánticos son otro modelo de cálculo que es inherentemente probabilístico.
