Teorema de Savitch (1970):
NESPACIO (f(n)) ⊆ DESPACIO ( f² (n)).Es decir, si una máquina de Turing no determinista puede resolver un problema usando memoria f ( n ), entonces una máquina de Turing determinista puede hacerlo por el cuadrado de la memoria.
| Prueba: |
| Considere una máquina de Turing con una entrada y una cinta de trabajo. Su configuración se puede codificar de la siguiente manera: codificar la posición y el contenido de la cinta de trabajo (ocupa memoria), la posición de la cinta de entrada (ocupa memoria). Dado que , el tamaño de la configuración será .
Dejar . Luego hay una máquina de Turing no determinista que reconoce este lenguaje. Considere una función auxiliar que calcula la posibilidad de transición de configuración a configuración en no más de transiciones: Alcance (I, J, k): si (k = 0) regresa (IJ) o (I = J) // registro (IJ) significa la capacidad de mover el MT de la configuración I a la configuración J en un solo paso else for (Y) // enumera configuraciones intermedias if Reach(I, Y, k-1) y Reach(Y, J, k-1) devuelven verdadero devuelven falsoEsta función tiene una profundidad de recursión, en cada nivel de recursión utiliza la memoria para almacenar las configuraciones actuales. Considere una máquina de Turing que reconoce un idioma. Esta máquina puede tener configuraciones. Esto se explica de la siguiente manera. Que tenga estados y símbolos del alfabeto de cinta. El número de líneas diferentes que pueden aparecer en la cinta de trabajo. El cabezal de la cinta de entrada puede estar en una de las posiciones y en una de las cintas de trabajo. Por lo tanto, el número total de todas las configuraciones posibles no supera . Considere una función que, dada una palabra dada, verifica si pertenece al idioma: Comprobar (x, L): para (T) // iterar sobre configuraciones que contienen estados de aceptación si Reach(S, T, ) devuelve verdadero devuelve falsoSi la palabra pertenece al idioma, entonces será admitida, ya que se considerarán todas las vías posibles de admisión. Esto lo proporciona la profundidad de recursión especificada para nosotros para la función. Y si no se permite una palabra por paso (el número de todas las configuraciones posibles), se garantiza que no se permitirá. Como resultado, la función tiene una profundidad de recurrencia, en cada nivel de memoria de recurrencia que se utiliza. Entonces toda esta función usa memoria. |