Máquina de Turing probabilística

---

En informática teórica , una máquina de Turing probabilística es una máquina de Turing no determinista que elige entre las transiciones disponibles en cada punto de acuerdo con alguna distribución de probabilidad . Como consecuencia, una máquina de Turing probabilística puede, a diferencia de una máquina de Turing determinista, tener resultados estocásticos ; es decir, en una máquina de estado de entrada e instrucción dada, puede tener diferentes tiempos de ejecución, o puede no detenerse en absoluto; además, puede aceptar una entrada en una ejecución y rechazar la misma entrada en otra ejecución.

En el caso de probabilidades iguales para las transiciones, las máquinas de Turing probabilísticas se pueden definir como máquinas de Turing deterministas que tienen una instrucción de "escritura" adicional donde el valor de la escritura se distribuye uniformemente en el alfabeto de la máquina de Turing (generalmente, una probabilidad igual de escribir una "1" o un "0" en la cinta). Otra reformulación común es simplemente una máquina de Turing determinista con una cinta añadida llena de bits aleatorios llamada "cinta aleatoria".

Una máquina de Turing probabilística es un tipo de máquina de Turing no determinista en la que cada paso no determinista es un "lanzamiento de moneda", es decir, en cada paso hay dos posibles movimientos siguientes y la máquina de Turing selecciona probabilísticamente qué movimiento tomar. ^[1]

Una máquina de Turing probabilística se puede definir formalmente como la 7-tupla , donde${\displaystyle M=(Q,\Sigma ,\Gamma ,q_{0},A,\delta _{1},\delta _{2})}$

En cada paso, la máquina de Turing aplica probabilísticamente la función de transición o la función de transición . ^[2] Esta elección se hace independientemente de todas las elecciones anteriores. De esta forma, el proceso de seleccionar una función de transición en cada paso del cálculo se asemeja a un lanzamiento de moneda.${\ estilo de visualización \ delta _ {1}}$${\ estilo de visualización \ delta _ {2}}$

La selección probabilística de la función de transición en cada paso introduce un error en la máquina de Turing; es decir, las secuencias que la máquina de Turing debe aceptar pueden rechazarse en algunas ocasiones y las secuencias que la máquina de Turing debe rechazar pueden aceptarse en algunas ocasiones. Para acomodar esto, se dice que un idioma es reconocido con probabilidad de error por una máquina de Turing probabilística si:${\displaystyle L}$${\displaystyle \epsilon }$${\displaystyle M}$

---