En la complejidad computacional , un campo de la informática , las máquinas de Turing de acceso aleatorio son una extensión de las máquinas de Turing utilizadas para hablar sobre clases de pequeña complejidad, especialmente para clases que usan tiempo logarítmico , como DLOGTIME y la jerarquía logarítmica .
Definición
En una máquina de Turing de acceso aleatorio, hay una cinta indicadora especial de espacio logarítmico que acepta un vocabulario binario. La máquina de Turing tiene un estado especial de tal manera que cuando el número binario en el puntero de la cinta es 'p', la máquina de Turing escribirá en la cinta de trabajo del p para el símbolo de la entrada.
La función de cinta de puntero permite que la máquina de Turing lea cualquier letra de la entrada sin tomarse el tiempo para desplazarse por toda la entrada. Esto es obligatorio para las clases de complejidad que utilizan menos tiempo lineal .
Referencias
- Complejidad descriptiva de Neil Immerman (Springer 1999), capítulo 5