Teorema de aceleración lineal

Aceleración de las máquinas de Turing mediante el aumento de la complejidad de los símbolos de cinta

En la teoría de la complejidad computacional , el teorema de aceleración lineal para las máquinas de Turing establece que, dado cualquier valor real c  > 0 y cualquier máquina de Turing de k -cintas que resuelva un problema en un tiempo f ( n ), existe otra máquina de k -cintas que resuelve el mismo problema en un tiempo como máximo f ( n )/ c + 2 n + 3 , donde k  > 1. ^{[1] [2]} Si la máquina original no es determinista , entonces la nueva máquina también es no determinista. Las constantes 2 y 3 en 2 n  + 3 se pueden reducir, por ejemplo, a n  + 2. ^[1]

Prueba

La construcción se basa en empaquetar 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 los 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.

Supongamos 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 de los símbolos empaquetados. La nueva máquina tiene la misma cantidad k  > 1 de cintas. Un estado de N consta de los siguientes componentes: ${\displaystyle \Sigma \cup \Sigma ^{3}}$

• el estado de M ;
• para cada cinta, tres símbolos empaquetados que describen el símbolo empaquetado debajo del encabezado, el símbolo empaquetado a la izquierda y el símbolo empaquetado a la derecha; y
• Para cada cinta, la posición original de la cabeza dentro del símbolo empaquetado debajo de la cabeza de N.

La nueva máquina N comienza codificando la entrada dada en un nuevo alfabeto (por eso su alfabeto debe incluir ). Por ejemplo, si la entrada a la cinta 2 M está a la izquierda, entonces después de la codificación la configuración de la cinta de N está a la derecha: ${\displaystyle \Sigma }$

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 símbolo nuevo (aquí (_, a , b )) y lo copia en la segunda cinta, mientras borra la primera. Al final de la inicialización, la nueva máquina dirige su cabezal al principio. En total, esto lleva 2 n  + 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 la cabeza de la máquina original apunta a los primeros símbolos dentro de y . Ahora la máquina comienza a simular m  = 3 transiciones de M utilizando 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 : ${\displaystyle (q_{0};~~~?,(\_,\_,\_),?;~~~?,(\_,a,b),?;~~~[1,1])}$ ${\displaystyle ?}$ ${\displaystyle [1,1]}$ ${\displaystyle (\_,\_,\_)}$ ${\displaystyle (\_,a,b)}$

donde los símbolos en negrita indican la posición de la cabeza. El estado de N es . Ahora sucede lo siguiente: ${\displaystyle (q;~~~?,(\_,\_,b),?;~~~?,(b,\_,\_),?;~~~[3,1])}$

• N se mueve a la derecha, izquierda, izquierda, derecha. Después de los cuatro movimientos, la máquina N tiene todo lleno y su estado pasa a ser ${\displaystyle ?}$ ${\displaystyle (q;~~~\#,(\_,\_,b),(b,a,b);~~~(b,a,b),(b,\_,\_),(\_,\_,\_);~~~[3,1])}$
• Ahora N actualiza sus símbolos y estado de acuerdo con m  = 3 transiciones de la máquina original. Esto puede requerir dos movimientos (actualizar el símbolo actual y actualizar 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):

Por lo tanto, el estado de N se convierte en . ${\displaystyle (q';~~~?,(\_,\_,b),?;~~~?,(b,\_,\_),?;~~~[3,1])}$

Complejidad

La inicialización requiere 2 n  + 3 pasos. En la simulación, 6 pasos de N simulan m pasos de M. Elegir m > 6 c produce el tiempo de ejecución limitado por ${\displaystyle f(n)/c+2n+3.}$

Máquinas con cinta de entrada de solo lectura

El teorema mencionado anteriormente también es válido para las máquinas de Turing con cinta de entrada y cinta de trabajo unidireccional de solo lectura . ^[3] ${\displaystyle k\geq 1}$

Maquinas de cinta simple

En el caso de las máquinas de Turing de una sola cinta, la aceleración lineal se cumple para máquinas con un tiempo de ejecución de al menos . Es demostrable que no se cumple para máquinas con un tiempo de . ^[3] ${\displaystyle n^{2}}$ ${\displaystyle t(n)\in \Omega (n\log n)\cap o(n^{2})}$

Dependencia de la compresión de cinta

La prueba del teorema de aceleración depende claramente de la capacidad de comprimir el almacenamiento reemplazando el alfabeto por uno más grande. Geffert ^[4] demostró que para máquinas de Turing de cinta única no deterministas con complejidad temporal se puede lograr una aceleración lineal sin aumentar el alfabeto. ${\displaystyle T(n)\geq n^{2}}$

Dependencia de la forma de almacenamiento

Regan ^[5] consideró una propiedad de un modelo computacional llamada vecindad de información. Esta propiedad está relacionada con la estructura de la memoria: una máquina de Turing tiene vecindad lineal, mientras que una máquina de Kolmogorov-Uspenskii y otras máquinas de puntero tienen una exponencial. La tesis de Regan es que la existencia de aceleración lineal tiene que ver con tener una vecindad de información polinómica. El punto sobresaliente en esta afirmación es que un modelo con vecindad exponencial no tendrá aceleración incluso si se permite cambiar el alfabeto (para modelos con una memoria discreta que almacena símbolos). Sin embargo, Regan no demostró ningún teorema general de este tipo. Hühne ^[6] demostró que si requerimos que la aceleración se obtenga mediante una simulación en línea (que es el caso de la aceleración en las máquinas de Turing ordinarias), entonces la aceleración lineal no existe en máquinas con almacenamiento en árbol .

Referencias

1. Christos Papadimitriou (1994). "2.4. Aceleración lineal". Complejidad computacional . Addison-Wesley.
2. 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.
3. Wagner, K.; Wechsung, G. (1986). Complejidad computacional . Springer. ISBN 978-9027721464.
4. Geffert, Viliam (1993). "Un teorema de aceleración sin compresión de cinta". Ciencias Informáticas Teóricas . 118 (1): 49–65. doi : 10.1016/0304-3975(93)90362-W .
5. Regan, Kenneth W. (1996). "Computación lineal en tiempo y con uso eficiente de la memoria". Revista SIAM de Computación . 25 (1): 133–168.
6. Hühne, Martin (1993). "La aceleración lineal no se mantiene en las máquinas de Turing con almacenamientos en árbol". Information Processing Letters . 47 (6): 313–318. doi :10.1016/0020-0190(93)90078-N.