Máquina probabilística de Turing
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 instrucción y entrada dada, puede tener diferentes tiempos de ejecución, o puede que no se detenga 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 probabilísticas de Turing 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 un "1" o un "0" en la cinta). Otra reformulación común es simplemente una máquina de Turing determinista con una cinta agregada 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 próximos movimientos y la máquina de Turing selecciona probabilísticamente cuál movimiento tomar. [1]
Una máquina de Turing probabilística se puede definir formalmente como la tupla 7 , donde
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 realiza independientemente de todas las elecciones anteriores. De esta manera, el proceso de seleccionar una función de transición en cada paso del cálculo se asemeja al lanzamiento de una moneda.
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 cadenas que la máquina de Turing debe aceptar pueden ser rechazadas en algunas ocasiones y las cadenas que la máquina de Turing debe rechazar pueden ser aceptadas en algunas ocasiones. Para adaptarse a esto, se dice que un lenguaje es reconocido con probabilidad de error por una máquina probabilística de Turing si:
