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 computadora cuántica es otro modelo de cálculo que es intrínsecamente 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 próximos movimientos y la máquina de Turing selecciona probabilísticamente cuál movimiento tomar. [1]
Definicion formal
Una máquina de Turing probabilística se puede definir formalmente como la tupla de 7 , dónde
- es un conjunto finito de estados
- es el alfabeto de entrada
- es un alfabeto de cinta, que incluye el símbolo en blanco
- es el estado inicial
- es el conjunto de estados de aceptación (final)
- es la primera función de transición probabilística. es un movimiento una celda a la izquierda en la cinta de la máquina de Turing y es un movimiento de una celda a la derecha.
- 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 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 está destinada a aceptar pueden ser rechazadas en algunas ocasiones y las cadenas que la máquina de Turing está destinada a rechazar pueden ser aceptadas en algunas ocasiones. Para adaptarse a esto, un idiomase dice que se reconoce con probabilidad de error por una máquina probabilística de Turing Si:
- una cuerda en implica que
- una cuerda no en implica que
Clases de complejidad
Como resultado del error introducido al utilizar lanzamientos probabilísticos de monedas, la noción de aceptación de una cuerda 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 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 de Turing probabilística en tiempo polinómico con una probabilidad de error de 1/3. Otra clase definida usando esta noción de aceptación es BPL , que es lo mismo que BPP pero coloca la restricción adicional de que los idiomas deben poder resolverse 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 está restringida al espacio logarítmico en lugar del tiempo polinomial, 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 máquina de prueba todopoderosa. 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 que se cree 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 un problema que pueda resolverse en tiempo polinomial mediante una máquina de Turing probabilística pero no una máquina de Turing determinista? ¿O pueden las máquinas de Turing deterministas simular de manera eficiente todas las máquinas de Turing probabilísticas 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 si (pero se sospecha ampliamente que) el BPP P , lo que implica que BPP = P . La misma pregunta para el espacio logarítmico en lugar del tiempo polinomial (¿ L = BPLP ?) Se cree incluso 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 de espacio-logarítmico, sugiere que la aleatoriedad puede agregar poder.
Ver también
Notas
- ^ Sipser, Michael (2006). Introducción a la Teoría de la Computación (2ª ed.). EE.UU .: Thomson Course Technology. pag. 368. ISBN 978-0-534-95097-2.
- ^ Arora, Sanjeev ; Barak, Boaz (2016). Complejidad computacional: un enfoque moderno . Prensa de la Universidad de Cambridge. pag. 125. ISBN 978-0-521-42426-4.
Referencias
- Arora, Sanjeev ; Barak, Boaz (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.). EE.UU .: Thomson Course Technology. págs. 368–380. ISBN 978-0-534-95097-2.