En la teoría de la complejidad computacional , el teorema de la aceleración lineal para las máquinas de Turing establece que dado cualquier c> 0 real y cualquier máquina de Turing de cinta k que resuelve un problema en el tiempo f (n) , hay otra máquina de cinta k que resuelve el mismo problema en tiempo como máximo f (n) / c + 2n + 3 , donde k> 1 . [1] [2] Si la máquina original no es determinista , entonces la nueva máquina tampoco es determinista. Las constantes concretas 2 y 3 en 2n + 3 se pueden reducir, por ejemplo, an + 2 . [1]
Prueba
La construcción se basa en el embalaje varios símbolos de cinta de la máquina original M en un símbolo de cinta de la nueva máquina N . Tiene un efecto similar al uso de palabras y comandos más largos en procesadores: acelera los cálculos pero aumenta el tamaño de la máquina. La cantidad de símbolos antiguos que se empaquetan en un símbolo nuevo depende de la aceleración deseada.
Suponga que la nueva máquina empaqueta tres símbolos antiguos en un símbolo nuevo. Entonces el alfabeto de la nueva máquina es: Consta de los símbolos originales y los símbolos empaquetados. La nueva máquina tiene el mismo número k> 1 de cintas. Un estado de N consta de los siguientes componentes:
- el estado de `` M '';
- para cada cinta: tres símbolos empaquetados que describen el símbolo empaquetado debajo de la cabeza, el símbolo empaquetado a la izquierda y el símbolo empaquetado a la derecha; y
- para cada cinta: la posición de la cabeza original dentro del símbolo lleno de debajo de la cabeza de N .
La nueva máquina N comienza codificando la entrada dada en un nuevo alfabeto (es por eso que su alfabeto debe incluir). Por ejemplo, si la entrada a 2 cintas M está a la izquierda, luego de la codificación, la configuración de cinta de N está a la derecha:
[# _ a B B a B B a _ ...] [# (_, _, _) (_, _, _) (_, _, _) ...] [# _ _ _ _ _ _ _ _ _ ...] [# (_, a, b) (b, a, b) (licenciado en Letras,_) ...]
La nueva máquina empaqueta tres símbolos antiguos (por ejemplo, el símbolo en blanco _ , el símbolo a y el símbolo b ) en un nuevo símbolo ( (_, a, b) ) y lo copia en la segunda cinta, mientras borra la primera cinta. Al final de la inicialización, la nueva máquina dirige su cabeza al principio. En general, esto requiere 2n + 3 pasos.
Después de la inicialización, el estado de N es, donde el símbolo significa que la máquina lo completará más tarde; el símbolo significa que el cabezal de la máquina original apunta a los primeros símbolos dentro y . Ahora la máquina comienza a simular m = 3 transiciones de M usando seis de sus propias transiciones (en este caso concreto, no habrá aceleración, pero en general m puede ser mucho mayor que seis). Sean las configuraciones de M y N :
[# _ _ B B a B B a _ ...] [# (_, a, b) (b, a, b) ( b , _, _) ...] [# _ a B B a B B _ _ ...] [# (_, _, b ) (b, a, b) (licenciado en Letras,_) ...]
donde los símbolos en negrita indican la posición de la cabeza. El estado de N es. Ahora sucede lo siguiente:
- N se mueve a la derecha, izquierda, izquierda, derecha. Después de los cuatro movimientos, la máquina N tiene todas sus lleno, y su estado se vuelve
- Ahora N actualiza sus símbolos y estado de acuerdo con m = 3 transiciones de la máquina original. Esto puede requerir dos movimientos (actualice el símbolo actual y actualice uno de sus símbolos adyacentes). Supongamos que la máquina original se mueve de la siguiente manera (con la configuración correspondiente de N a la derecha):
[# _ _ _ _ _ B B a _ ...] [# (_, a, b) ( b , _, _) (_, _, _) ...] [# _ a B B _ _ _ _ _ ...] [# (_, _, _) (_, _, b ) (licenciado en Letras,_) ...]
Por tanto, el estado de N se convierte en.
Complejidad
La inicialización requiere 2n + 3 pasos. En la simulación, 6 pasos de N simulan m etapas de M . Elegir m> 6c produce el tiempo de ejecución.
Referencias
- ↑ a b Christos Papadimitriou (1994). "2.4. Aceleración lineal". Complejidad computacional . Addison-Wesley.
- ^ Thomas A. Sudkamp (1994). "14.2 Aceleración lineal". Lenguajes y máquinas: una introducción a la teoría de la informática . Addison-Wesley.