Máquina probabilística de Turing

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 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 determinada máquina de estado de entrada y de instrucción, 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 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 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 siguientes movimientos posibles y la máquina de Turing selecciona probabilísticamente qué movimiento realizar. ^[1]

Definicion formal

Una máquina probabilística de Turing se puede definir formalmente como la tupla 7 , 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 aceptantes (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 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 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 error en la máquina de Turing; es decir, las cadenas que la máquina de Turing debe aceptar pueden en algunas ocasiones ser rechazadas y las cadenas que la máquina de Turing debe rechazar pueden en algunas ocasiones aceptarse. Para dar cabida a esto, se dice que un lenguaje es reconocido con probabilidad de error por una máquina probabilística de Turing si: ${\displaystyle L}$ ${\displaystyle \epsilon }$ ${\displaystyle M}$

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

Clases de complejidad

Problema no resuelto en informática :

¿Es 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 probabilística de Turing se puede definir de diferentes maneras. Una de esas nociones que incluye varias clases de complejidad importantes es permitir 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 probabilística de Turing en tiempo polinómico con una probabilidad de error de 1/3. Otra clase definida utilizando esta noción de aceptación es BPL , que es lo mismo que BPP pero impone la restricción adicional de que los lenguajes deben poder resolverse en un 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 polinómico, se obtienen las clases de complejidad análogas RL , co-RL y ZPL . Al hacer cumplir 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 probadora. Por ejemplo, la clase IP es igual a PSPACE , pero si se elimina la aleatoriedad del verificador, solo nos queda NP , que no se conoce pero se cree ampliamente que es una clase considerablemente más pequeña.

Una de las cuestiones centrales de la teoría de la complejidad es si la aleatoriedad añade poder; es decir, ¿existe algún problema que pueda resolverse en tiempo polinomial mediante una máquina de Turing probabilística pero no con una máquina de Turing determinista? ¿O pueden las máquinas deterministas de Turing simular eficientemente todas las máquinas probabilísticas de Turing con como máximo una desaceleración polinómica? 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 está claro (aunque se sospecha ampliamente que) BPP ⊆ P , lo que implica que BPP = P . Se cree aún más que es cierta la misma pregunta para el espacio logarítmico en lugar del tiempo polinómico (¿ L = BPLP ?). 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 gráficos en espacio logarítmico, sugiere que la aleatoriedad puede agregar poder.

Ver también

• Algoritmo aleatorio

Notas

1. Sipser, Michael (2006). Introducción a la Teoría de la Computación (2ª ed.). Estados Unidos: Tecnología del curso Thomson. pag. 368.ISBN​ 978-0-534-95097-2.
2. Arora, Sanjeev ; Barac, Booz (2016). Complejidad computacional: un enfoque moderno . Prensa de la Universidad de Cambridge. pag. 125.ISBN​ 978-0-521-42426-4.

Referencias

• Arora, Sanjeev ; Barac, Booz (2016). Complejidad computacional: un enfoque moderno . Prensa de la Universidad de Cambridge. 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.). Estados Unidos: Tecnología del curso Thomson. págs. 368–380. ISBN 978-0-534-95097-2.

enlaces externos

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