Máquina de Turing probabilística

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 puede 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 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.

Véase también

• Máquina de Turing
• Máquina universal de Turing
• Máquina de Turing alternante
• Alan Turing

Enlaces externos

• NIST Página sobre máquinas de Turing probabilísticas

Esta página se editó por última vez el 14 ago 2020 a las 03:22.