Máquina de Turing probabilística

Modelo matemático de computación

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 puede, a diferencia de una máquina de Turing determinista, tener resultados estocásticos ; es decir, en una máquina de estados 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 pueden definirse 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 adicional llena de bits aleatorios llamada "cinta aleatoria".

Una computadora cuántica es otro modelo de computación que es inherentemente probabilístico.

Descripción

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 realizar. ^[1]

Definición formal

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})}$

• ${\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\subseteq 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. es un movimiento de una celda hacia la izquierda en la cinta de la máquina de Turing y es un movimiento de una celda hacia la derecha. ${\displaystyle L}$ ${\displaystyle R}$
• ${\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 de manera probabilística 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 selección de una función de transición en cada paso del cálculo se asemeja al lanzamiento de una moneda. ${\displaystyle \delta _{1}}$ ${\displaystyle \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 cadenas que la máquina de Turing debería aceptar pueden ser rechazadas en algunas ocasiones y las cadenas que la máquina de Turing debería rechazar pueden ser aceptadas en algunas ocasiones. Para dar cabida a esto, se dice que una máquina de Turing probabilística reconoce un lenguaje con probabilidad de error si: ${\displaystyle L}$ ${\displaystyle \epsilon }$ ${\displaystyle M}$

1. una cadena en implica que ${\displaystyle w}$ ${\displaystyle L}$ ${\displaystyle {\text{Pr}}[M{\text{ accepts }}w]\geq 1-\epsilon }$
2. una cadena no implica que ${\displaystyle w}$ ${\displaystyle L}$ ${\displaystyle {\text{Pr}}[M{\text{ rejects }}w]\geq 1-\epsilon }$

Clases de complejidad

Problema sin resolver en informática :

¿ P = BPP  ?

(más problemas sin resolver en informática)

Como resultado del error introducido al utilizar lanzamientos probabilísticos de monedas, la noción de aceptación de una cadena por una máquina de Turing probabilística puede definirse de diferentes maneras. Una de esas nociones que incluye varias clases de complejidad importantes es la que permite una probabilidad de error de 1/3. Por ejemplo, la clase de complejidad BPP se define como la clase de idiomas 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 la misma que BPP pero impone la restricción adicional de que los idiomas deben ser resolubles en el 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 aplicar ambas restricciones, se obtienen RLP , co-RLP , BPLP y ZPLP .

El cálculo probabilístico 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 de prueba. Por ejemplo, la clase IP es igual a PSPACE , pero si se elimina la aleatoriedad del verificador, nos quedamos solo con NP , que no se conoce 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 agrega poder; es decir, ¿existe un problema que pueda ser resuelto en tiempo polinomial por una máquina de Turing probabilística pero no por una máquina de Turing determinista? ¿O pueden las máquinas de Turing deterministas simular eficientemente todas las máquinas de Turing probabilísticas con, como máximo, una desaceleración polinomial? Se sabe que P ⊆ BPP , ya que una máquina de Turing determinista es solo un caso especial de una máquina de Turing probabilística. Sin embargo, no se sabe con certeza si BPP ⊆ P (aunque se sospecha ampliamente que sí) , lo que implica que BPP = P . La misma pregunta para el espacio logarítmico en lugar del tiempo polinomial (¿ L = BPLP ?) se cree aún más ampliamente que es cierta. Por otro lado, el poder que la aleatoriedad otorga a los sistemas de prueba interactivos, así como los algoritmos simples que crea para problemas difíciles como las pruebas de primalidad en tiempo polinomial y las pruebas de conectividad de grafos en el espacio logarítmico, sugieren que la aleatoriedad puede agregar poder.

Véase también

• Algoritmo aleatorio

Notas

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

Referencias

• Arora, Sanjeev ; Barak, Boaz (2016). Complejidad computacional: un enfoque moderno . Cambridge University Press. págs. 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. pp. 368–380. ISBN 978-0-534-95097-2.

Enlaces externos

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