En informática teórica, el modelo de máquina de programa almacenado de acceso aleatorio (RASP) es una máquina abstracta utilizada para el desarrollo de algoritmos y la teoría de la complejidad de algoritmos .
El RASP es un modelo de máquina de acceso aleatorio (RAM) que, a diferencia de la RAM, tiene su programa en sus "registros" junto con su entrada. Los registros son ilimitados (infinitos en capacidad); si el número de registros es finito o no es específico del modelo. Por lo tanto, el RASP es a la RAM lo que la máquina universal de Turing es a la máquina de Turing . El RASP es un ejemplo de la arquitectura de von Neumann, mientras que la RAM es un ejemplo de la arquitectura de Harvard .
El RASP es el modelo abstracto más cercano a la noción común de computadora . Pero a diferencia de las computadoras reales, el modelo RASP generalmente tiene un conjunto de instrucciones muy simple, muy reducido de los procesadores CISC e incluso RISC a las operaciones aritméticas más simples, "movimientos" de registro a registro e instrucciones de "prueba/salto". Algunos modelos tienen algunos registros adicionales, como un acumulador .
Junto con la máquina de registro , la RAM y la máquina de puntero , el RASP constituye los cuatro modelos comunes de máquinas secuenciales, llamados así para distinguirlos de los modelos "paralelos" (por ejemplo, la máquina de acceso aleatorio paralela ) [cf. van Emde Boas (1990)].
Descripción resumida de un RASP:
El lector recordará que la UTM es una máquina de Turing con una tabla de instrucciones de estados finitos "universal" que puede interpretar cualquier "programa" bien formado escrito en la cinta como una cadena de 5-tuplas de Turing, de ahí su universalidad. Mientras que el modelo UTM clásico espera encontrar 5-tuplas de Turing en su cinta, cualquier conjunto de programas imaginable puede colocarse allí, dado que la máquina de Turing espera encontrarlos, dado que su tabla de estados finitos puede interpretarlos y convertirlos en la acción deseada. Junto con el programa, impresos en la cinta estarán los datos/parámetros/números de entrada (normalmente a la derecha del programa) y, finalmente, los datos/números de salida (normalmente a la derecha de ambos, o entremezclados con la entrada, o reemplazándola). El "usuario" debe colocar la cabeza de la máquina de Turing sobre la primera instrucción, y la entrada debe colocarse en un lugar específico y en un formato apropiado tanto para el programa en la cinta como para la tabla de instrucciones de la máquina de estados finitos.
El RASP imita esta construcción: coloca el "programa" y los "datos" en los agujeros (registros). Pero a diferencia del UTM, el RASP procede a "buscar" sus instrucciones de manera secuencial, a menos que la prueba condicional las envíe a otra parte.
Un punto de confusión: dos conjuntos de instrucciones : a diferencia del UTM, el modelo RASP tiene dos conjuntos de instrucciones: la tabla de instrucciones de la máquina de estados (el "intérprete") y el "programa" en los agujeros. Los dos conjuntos no tienen por qué extraerse del mismo conjunto.
El siguiente ejemplo de un programa moverá el contenido del registro (agujero) #18 al registro (agujero) #19, borrando el contenido del #18 en el proceso.
5: 03 18 15 JZ 18 , 15 ; si [18] es cero, salta a 15 para finalizar el programa 02 18 DEC 18 ; Decrementa [18] 01 19 INC 19 ; Incrementa [19] 03 15 05 JZ 15 , 5 ; Si [15] es cero, salta a 5 para repetir el bucle (usa Detener para simular un salto incondicional) 15: 00 H ; Detener 18: n ; Valor de origen para copiar 19: ; Destino para la copia Las instrucciones del programa disponibles en esta máquina RASP serán un conjunto simple para que el ejemplo sea breve:
Para facilitar el ejemplo, equiparemos la máquina de estados de la RAM como RASP con las instrucciones primitivas extraídas del mismo conjunto, pero aumentadas con dos instrucciones de copia indirecta:
Mientras la máquina de estados de la máquina RASP interpreta el programa en los registros, ¿qué hará exactamente la máquina de estados? La columna que contiene el signo de exclamación ! enumerará en secuencia temporal las acciones de la máquina de estados a medida que "interpreta" (convierte en acción) el programa:
La tradición divide las acciones de la máquina de estados en dos "fases" principales llamadas Fetch y Execute . Observaremos a continuación que existen "subfases" dentro de estas dos fases principales. No existe una convención acordada; cada modelo requerirá su propia descripción precisa.
La máquina de estados tiene acceso a todos los registros, tanto directa como indirectamente. Por lo tanto, adopta el número 1 como "el contador de programa" PC. La función del contador de programa será "mantener el lugar" en la lista del programa; la máquina de estados tiene su propio registro de estado para su uso privado.
Al iniciarse, la máquina de estados espera encontrar un número en la PC: la primera "Instrucción de programa" en el programa (es decir, el n.° 5).
(Sin el uso de COPIAS indirectas, la tarea de llevar la instrucción del programa apuntada al n.° 2 es un poco ardua. La máquina de estados decrementaría indirectamente el registro apuntado mientras incrementa directamente el registro (vacío) n.° 2. Durante la fase de "análisis", restaurará el contenido sacrificado del n.° 5 sacrificando el conteo en el n.° 2).
El objetivo del desvío anterior es mostrar que la vida es mucho más fácil cuando la máquina de estados tiene acceso a dos tipos de copia indirecta:
El siguiente ejemplo muestra lo que sucede durante la fase de "búsqueda" de la máquina de estados. Las operaciones de la máquina de estados se enumeran en la columna denominada "Instrucción de máquina de estados ↓". Observe que al final de la búsqueda, el registro n.° 2 contiene el valor numérico 3 del "código de operación" ("opcode") de la primera instrucción JZ :
Ahora que el número de la instrucción del programa (por ejemplo, 3 = "JZ") está en el registro n.° 2 (el "Registro de instrucción del programa" PIR), la máquina de estados procede a decrementar el número hasta que el IR esté vacío:
Si el IR estuviera vacío antes del decremento, entonces la instrucción del programa sería 0 = HALT y la máquina saltaría a su rutina "HALT". Después del primer decremento, si el agujero estuviera vacío, la instrucción sería INC y la máquina saltaría a la instrucción "inc_routine". Después del segundo decremento, el IR vacío representaría DEC y la máquina saltaría a la "dec_routine". Después del tercer decremento, el IR está realmente vacío y esto provoca un salto a la rutina "JZ_routine". Si todavía hubiera un número inesperado en el IR, entonces la máquina habría detectado un error y podría HALT (por ejemplo).
Ahora la máquina de estados sabe qué instrucción de programa ejecutar; de hecho, ha saltado a la secuencia de instrucciones "JZ_routine". La instrucción JZ tiene dos operandos: (i) el número del registro que se va a probar y (ii) la dirección a la que se debe ir si la prueba es exitosa (el agujero está vacío).
(i) Obtención de operandos: ¿qué registro comprobar si está vacío?: De manera análoga a la fase de obtención, la máquina de estados finitos mueve el contenido del registro al que apunta la PC, es decir, el agujero n.° 6, al registro de instrucción de programa PIR n.° 2. Luego, utiliza el contenido del registro n.° 2 para señalar el registro que se comprobará si está cero, es decir, el registro n.° 18. El agujero n.° 18 contiene un número "n". Para realizar la prueba, ahora la máquina de estados utiliza el contenido del PIR para copiar indirectamente el contenido del registro n.° 18 en un registro de repuesto, el n.° 3. Por lo tanto, hay dos eventualidades (ia), el registro n.° 18 está vacío, (ib) el registro n.° 18 no está vacío.
(ia): Si el registro n.° 3 está vacío, la máquina de estados salta a (ii) Búsqueda del segundo operando: busca la dirección de salto.
(ib): Si el registro n.° 3 no está vacío, la máquina de estados puede omitir (ii) la obtención del segundo operando. Simplemente incrementa el PC al doble y luego vuelve incondicionalmente a la fase de obtención de instrucciones, donde obtiene la instrucción de programa n.° 8 (DEC).
(ii) Obtención de operandos: salto a la dirección . Si el registro n.° 3 está vacío, la máquina de estados procede a utilizar el PC para copiar indirectamente el contenido del registro al que apunta (n.° 8) en sí misma . Ahora el PC tiene la dirección de salto 15. Luego, la máquina de estados vuelve incondicionalmente a la fase de obtención de instrucciones, donde obtiene la instrucción de programa n.° 15 (HALT).
Lo siguiente completa la interpretación de la máquina de estados de la RAM de las instrucciones del programa, INC h, DEC h y, por lo tanto, completa la demostración de cómo una RAM puede "hacerse pasar por" un RASP:
Sin las instrucciones de máquina de estados indirectas INCi y DECi, para ejecutar las instrucciones de programa INC y DEC, la máquina de estados debe usar la copia indirecta para obtener el contenido del registro señalado en el registro libre n.° 3, DEC o INC, y luego usar la copia indirecta para enviarlo de regreso al registro señalado.
Instrucciones alternativas : Aunque la demostración dio como resultado un RASP primitivo de sólo cuatro instrucciones, el lector podría imaginar cómo podría realizarse una instrucción adicional como "ADD ⟨h⟩ " o "MULT ⟨h a ⟩ ,⟪h b >.
Cuando una RAM actúa como un RASP, se ha obtenido algo nuevo: a diferencia de la RAM, el RASP tiene la capacidad de automodificar sus instrucciones de programa (las instrucciones de la máquina de estados están congeladas, y la máquina no puede modificarlas). Cook-Reckhow (1971) (p. 75) comenta esto en su descripción de su modelo RASP, al igual que Hartmanis (1971) (pp. 239ff).
Una descripción temprana de esta noción se puede encontrar en Goldstine-von Neumann (1946):
Esta capacidad permite lo siguiente:
En un artículo influyente, Stephen A. Cook y Robert A. Reckhow definen su versión de un RASP:
Su propósito era comparar los tiempos de ejecución de varios modelos: RAM, RASP y máquina de Turing multicinta para su uso en la teoría del análisis de la complejidad .
La característica más destacada de su modelo RASP es que no prevé instrucciones indirectas para el programa (véase su discusión en la página 75). Esto lo logran al exigir que el programa se modifique a sí mismo: si es necesario, una instrucción puede modificar el "parámetro" (su palabra, es decir, el "operando") de una instrucción en particular. Han diseñado su modelo de modo que cada "instrucción" utilice dos registros consecutivos, uno para el "código de operación" (su palabra) y el parámetro "ya sea una dirección o una constante entera".
Los registros de su RASP no tienen límite de capacidad ni de número; de la misma manera, su acumulador AC y su contador de instrucciones IC no tienen límite. El conjunto de instrucciones es el siguiente:
A menudo, las máquinas RAM y RASP se presentan juntas en el mismo artículo. Estas se han copiado de Random-access machine ; con algunas excepciones, estas referencias son las mismas que las de Register machine .