Una máquina de Turing simétrica es una máquina de Turing que tiene un gráfico de configuración que no está dirigido (es decir, la configuración i produce la configuración j si y solo si j produce i).
Definición de máquinas de Turing simétricas
Formalmente, definimos una variante de las máquinas de Turing con un conjunto de transiciones de la forma (p, ab, D, cd, q) , donde p, q son estados, ab, cd son pares de símbolos y D es una dirección. Si se deja D , entonces el cabezal de una máquina en el estado p encima de un símbolo de cinta b precedido por un símbolo a se puede cambiar moviendo el cabezal hacia la izquierda, cambiando el estado a q y reemplazando el símbolo a, b por c, d . Siempre se puede aplicar la transición opuesta (q, cd, -D, ab, p) . Si D tiene razón, la transición es análoga. La capacidad de mirar dos símbolos y cambiar ambos a la vez no es esencial, pero facilita la definición.
Estas máquinas fueron definidas por primera vez en 1982 por Harry R. Lewis y Christos Papadimitriou , [1] [2] que buscaban una clase en la que colocar USTCON , el problema preguntaba si hay una ruta entre dos vértices dados s, t en un gráfico no dirigido. Hasta ese momento, solo podía colocarse en NL , a pesar de que aparentemente no requería no determinismo ( se sabía que la variante asimétrica STCON estaba completa para NL). Las máquinas de Turing simétricas son una especie de máquinas de Turing con un poder no determinista limitado, y se demostró que eran al menos tan poderosas como las máquinas de Turing deterministas, lo que proporciona un caso interesante en el medio.
STIME (T (n)) es la clase de lenguajes aceptados por una máquina de Turing simétrica que se ejecuta en el tiempo O (T (n)). Puede probar fácilmente que STIME (T) = NTIME (T) limitando el no determinismo de cualquier máquina en NTIME (T) a una etapa inicial en la que una cadena de símbolos se escribe de forma no determinista, seguida de cálculos deterministas.
SL = L
SSPACE (S (n)) es la clase de lenguajes aceptados por una máquina de Turing simétrica que se ejecuta en el espacio O (S (n)) y SL = SSPACE (log (n)).
SL se puede definir de manera equivalente como la clase de problemas de espacio de registro reducible a USTCON. Lewis y Papadimitriou, por su definición, demostraron esto al construir una máquina no determinista para USTCON con propiedades que demostraron que son suficientes para hacer posible la construcción de una máquina de Turing simétrica equivalente. Luego, observaron que cualquier lenguaje en SL es logspace reducible a USTCON ya que a partir de las propiedades del cálculo simétrico podemos ver la configuración especial como los bordes no dirigidos del gráfico.
En 2004, Omer Reingold demostró que SL = L mostrando un algoritmo determinista para USTCON que se ejecuta en espacio logarítmico, [3] por el que recibió el premio Grace Murray Hopper 2005 y (junto con Avi Wigderson y Salil Vadhan ) el premio Gödel 2009 . La prueba utiliza el producto en zig-zag para construir de manera eficiente gráficos de expansión .
Notas
- ^ Jesper Jansson. Algoritmos deterministas de conectividad de gráficos limitados por el espacio . Manuscrito. 1998.
- ^ Harry R. Lewis y Christos H. Papadimitriou. Cálculo simétrico delimitado por el espacio. Informática Teórica . pp.161-187. mil novecientos ochenta y dos.
- ^ Reingold, Omer (2008), "Conectividad no dirigida en el espacio de registro", Diario del ACM , 55 (4): 1–24, doi : 10.1145 / 1391289.1391291 , MR 2445014 , ECCC TR04-094
Referencias
- Notas de la conferencia: CS369E: Expansores en Ciencias de la Computación Por Cynthia Dwork y Prahladh Harsha
- Notas de lectura
- Notas de la conferencia de Sharon Bruckner
- Algoritmos de conectividad Deterministic Space Bounded Graph Jesper Janson