Teorema de aceleración lineal

En la teoría de la complejidad computacional , el teorema de aceleración lineal para máquinas de Turing establece que, dado cualquier número real c  >  0 y cualquier máquina de Turing de k cintas que resuelve un problema en tiempo f ( n ), existe otra máquina de k cintas que resuelve el mismo problema en 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 lo es. Las constantes 2 y 3 en 2 n + 3 se pueden reducir, por ejemplo, a n + 2. ^{[ 1 ]}

El teorema también se cumple para máquinas de Turing con cinta de entrada de solo lectura de una dirección y${\displaystyle k\geq 1}$cintas de trabajo. ^{[ 3 ]}

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

La construcción se basa en empaquetar varios símbolos de cinta de la máquina original M en un único símbolo de cinta de la nueva máquina N. Esto tiene un efecto similar al de usar 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 nuevo símbolo depende de la aceleración deseada.

Supongamos que la nueva máquina empaqueta tres símbolos antiguos en un nuevo símbolo. Entonces el alfabeto de la nueva máquina es${\displaystyle \Sigma \cup \Sigma ^{3}}$: 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 del cabezal, el símbolo empaquetado a la izquierda y el símbolo empaquetado a la derecha; y
• para cada cinta, la posición original del cabezal dentro del símbolo empaquetado debajo del cabezal de N.

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

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 (en este caso (_, a , b )) y lo copia en la segunda cinta, borrando la primera. Al finalizar la inicialización, la nueva máquina dirige su cabezal al principio. En total, esto requiere 2 n + 3 pasos.

Después de la inicialización, el estado de N es${\displaystyle (q_{0};~~~?,(\_,\_,\_),?;~~~?,(\_,a,b),?;~~~[1,1])}$donde el símbolo${\displaystyle$ ?} significa que la máquina lo rellenará más tarde; el símbolo${\displaystyle [1,1]}$significa que el cabezal de la máquina original apunta a los primeros símbolos dentro${\displaystyle (\_,\_,\_)}$y${\displaystyle (\_,a,b)}$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 :

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

• N se mueve derecha, izquierda, izquierda, derecha. Después de los cuatro movimientos, la máquina N tiene todos sus${\displaystyle$ ?} lleno, y su estado se convierte en${\displaystyle (q;~~~\#,(\_,\_,b),(b,a,b);~~~(b,a,b),(b,\_,\_),(\_,\_,\_);~~~[3,1])}$
• Ahora N actualiza sus símbolos y estado según 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):

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

La demostración del teorema de aceleración depende claramente de la capacidad de comprimir el almacenamiento reemplazando el alfabeto por uno más grande. Específicamente, depende del teorema de compresión de cinta : ^{[ 4 ] : Teorema 2.1, 2.2}

Si un idioma${\displaystyle L}$es aceptado por una máquina de Turing dentro del espacio${\displaystyle s(n)}$, entonces para cualquier${\displaystyle c>0}$, existe alguna máquina de Turing que lo acepta dentro del espacio${\displaystyle c\cdot s(n)}$Lo mismo ocurre con las máquinas de Turing no deterministas.

Para máquinas de Turing de cinta única no deterministas de complejidad temporal${\displaystyle T(n)\geq n^{2}}$, se puede lograr una aceleración lineal sin aumentar el alfabeto. ^{[ 5 ]}

Regan ^{[ 6 ]} consideró una propiedad de un modelo computacional llamada vecindad de información. Esta propiedad está relacionada con la estructura de memoria: una máquina de Turing tiene vecindad lineal, mientras que una máquina de Kolmogorov-Uspenskii y otras máquinas de punteros 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 polinomial. 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 ^{[ 7 ]} demostró que si requerimos que la aceleración se obtenga mediante una simulación en línea (que es el caso para la aceleración en máquinas de Turing ordinarias), entonces la aceleración lineal no existe en máquinas con almacenamiento de árbol .