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 según una distribución de probabilidad . En consecuencia, una máquina de Turing probabilística (a diferencia de una máquina de Turing determinista) puede tener resultados estocásticos ; es decir, para una entrada y una máquina de estados de instrucciones dadas, 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.

En el caso de probabilidades iguales para las transiciones, las máquinas de Turing probabilísticas pueden definirse como máquinas de Turing deterministas con una instrucción de "escritura" adicional, cuyo valor se distribuye uniformemente en el alfabeto de la máquina (generalmente, con la misma probabilidad de escribir un "1" o un "0" en la cinta). Otra reformulación común consiste simplemente en una máquina de Turing determinista con una cinta adicional llena de bits aleatorios, denominada "cinta aleatoria".

Una computadora cuántica (o máquina de Turing cuántica ) es otro modelo de computación que es inherentemente probabilístico .

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 cuál movimiento tomar. ^{[ 1 ]}

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

• ${\displaystyle Q}$es un conjunto finito de estados
• ${\displaystyle \Sigma }$es el alfabeto de entrada
• ${\displaystyle \Gamma }$es un alfabeto de cinta, que incluye el símbolo en blanco #
• ${\displaystyle q_{0}\in Q}$es el estado inicial
• ${\displaystyle A\subsetq Q}$es el conjunto de estados de aceptación (finales)
• ${\displaystyle \delta _{1}:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}}$es la primera función de transición probabilística.${\displaystyle L}$es un movimiento de una celda a la izquierda en la cinta de la máquina de Turing y${\displaystyle R}$es un movimiento de una celda a la derecha.
• ${\displaystyle \delta _{2}:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}}$es la segunda función de transición probabilística.

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

La selección probabilística de la función de transición en cada paso introduce errores en la máquina de Turing; es decir, las cadenas que la máquina de Turing debería aceptar pueden ser rechazadas en algunas ocasiones, y las cadenas que debería rechazar pueden ser aceptadas en otras. Para dar cabida a esto, se utiliza un lenguaje${\displaystyle L}$Se dice que se reconoce con probabilidad de error.${\displaystyle \epsilon }$mediante una máquina de Turing probabilística${\displaystyle M}$si:

1. una cuerda${\displaystyle w}$en${\displaystyle L}$implica que${\displaystyle {\text{Pr}}[M{\text{ acepta }}w]\geq 1-\epsilon }$
2. una cuerda${\displaystyle w}$no en${\displaystyle L}$implica que${\displaystyle {\text{Pr}}[M{\text{ rechaza }}w]\geq 1-\epsilon }$

Como resultado del error introducido al utilizar lanzamientos de moneda probabilísticos, la noción de aceptación de una cadena por una máquina de Turing probabilística puede definirse de diferentes maneras. Una de estas nociones, que incluye varias clases de complejidad importantes, permite una probabilidad de error de 1/3. Por ejemplo, la clase de complejidad BPP se define como la clase de lenguajes reconocidos por una máquina de Turing probabilística en tiempo polinomial con una probabilidad de error de 1/3. Otra clase definida utilizando esta noción de aceptación es BPL , que es igual a BPP pero impone la restricción adicional de que los lenguajes deben ser resolubles en espacio logarítmico .

Las clases de complejidad que surgen de otras definiciones de aceptación incluyen RP , co-RP y ZPP . Si la máquina se restringe al espacio logarítmico en lugar del tiempo polinomial, se obtienen las clases de complejidad análogas RL , co-RL y ZPL . Al imponer ambas restricciones, se obtienen RLP , co-RLP , BPLP y ZPLP .

La computación probabilística también es fundamental para la definición de la mayoría de las clases de sistemas de prueba interactivos , en los que la máquina verificadora depende de la aleatoriedad para evitar ser predicha y engañada por la todopoderosa máquina probadora. Por ejemplo, la clase IP es igual a PSPACE , pero si se elimina la aleatoriedad del verificador, nos queda solo NP , que se desconoce, pero se cree ampliamente que es una clase considerablemente más pequeña.

Una de las preguntas centrales de la teoría de la complejidad es si la aleatoriedad añade potencia; es decir, ¿existe algún problema que pueda resolverse en tiempo polinomial mediante una máquina de Turing probabilística pero no mediante una determinista? ¿O pueden las máquinas de Turing deterministas simular eficientemente todas las máquinas de Turing probabilísticas con una ralentización máxima de tiempo polinomial? Se sabe que P ⊆ BPP , puesto que una máquina de Turing determinista es simplemente un caso especial de una máquina de Turing probabilística. Sin embargo, no se sabe con certeza si (aunque se sospecha ampliamente que) BPP ⊆ P , lo que implicaría que BPP = P. La misma pregunta para el espacio logarítmico en lugar del tiempo polinomial (¿es L = BPLP ?) se considera aún más cierta. Por otro lado, la potencia que la aleatoriedad confiere a los sistemas de prueba interactivos, así como los algoritmos sencillos que crea para problemas difíciles como la prueba de primalidad en tiempo polinomial y la prueba de conectividad de grafos en espacio logarítmico, sugiere que la aleatoriedad puede añadir potencia.

• Algoritmo aleatorio

• Arora, Sanjeev ; Barak, Boaz (2016). Complejidad computacional: un enfoque moderno . Cambridge University Press. pp. 123–142 . ISBN  978-0-521-42426-4.
• Sipser, Michael (2006). Introducción a la teoría de la computación (2.ª  ed.). EE. UU.: Thomson Course Technology. págs. 368–380 . ISBN  978-0-534-95097-2.

• Sitio web del NIST sobre máquinas de Turing probabilísticas