Máquina de Turing simétrica

Una máquina de Turing simétrica es una máquina de Turing que tiene un gráfico de configuración no dirigido (es decir, la configuración i produce la configuración j si y solo si j produce i).

Formalmente, definimos una variante de las máquinas de Turing con un conjunto de transiciones de la forma ⁠ ⁠${\estilo de visualización (p,ab,D,cd,q)}$ , donde p,q son estados, ab,cd son pares de símbolos y D es una dirección. Si D es left , entonces la cabeza de una máquina en estado p sobre un símbolo de cinta b precedido por un símbolo a puede ser transicionado moviendo la cabeza hacia la izquierda, cambiando el estado a q y reemplazando los símbolos a,b por c,d . La transición opuesta ⁠ ⁠${\displaystyle (q,cd,-D,ab,p)}$ siempre puede aplicarse. Si D es right la transición es análoga. La capacidad de echar un vistazo a dos símbolos y cambiar ambos a la vez no es esencial, pero hace que la definición sea más fácil.

Estas máquinas fueron definidas por primera vez en 1982 por Harry R. Lewis y Christos Papadimitriou ^{[1] [2]} , quienes buscaban una clase en la que colocar USTCON , el problema que preguntaba si existe un camino entre dos vértices dados s,t en un grafo no dirigido. Hasta ese momento, solo se podía colocar en NL , a pesar de que aparentemente no requería no determinismo (se sabía que la variante asimétrica STCON era completa para NL). Las máquinas de Turing simétricas son un tipo de máquina de Turing con poder no determinista limitado, y se demostró que eran al menos tan poderosas como las máquinas de Turing deterministas, lo que brinda un caso interesante entre ellos.

⁠ ⁠${\displaystyle {\mathsf {TIEMPO}}(T(n))}$ es la clase de lenguajes aceptados por una máquina de Turing simétrica que funciona en el tiempo ⁠ ⁠${\displaystyle O(T(n))}$ . Se puede demostrar fácilmente que ⁠ ⁠${\displaystyle {\mathsf {TIEMPO}}(T)={\mathsf {TIEMPONTÍMETRO}}(T)}$ limitando el no determinismo de cualquier máquina en ⁠ ⁠${\displaystyle {\mathsf {TIEMPONT}}(T)}$ a una etapa inicial donde una cadena de símbolos se escribe de forma no determinista, seguida de cálculos deterministas.

SSPACE (S( n )) es la clase de lenguajes aceptados por una máquina de Turing simétrica que se ejecuta en el espacio ⁠ ⁠${\displaystyle O(S(n))}$ y SL = SSPACE (log( n )).

SL puede definirse de manera equivalente como la clase de problemas reducibles en el espacio logarítmico a USTCON. Lewis y Papadimitriou demostraron esto mediante su definición 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 reducible en el espacio logarítmico 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 grafo.

En 2004, Omer Reingold demostró que SL=L mostrando un algoritmo determinista para USTCON ejecutándose en el espacio logarítmico, ^[3] por el cual 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 eficientemente gráficos expansores .

• Notas de la clase: CS369E: Expansores en informática Por Cynthia Dwork y Prahladh Harsha
• Notas de la conferencia
• Notas de la conferencia de Sharon Bruckner
• Algoritmos de conectividad de gráficos deterministas acotados en el espacio Jesper Janson