En informática teórica, el modelo de máquina de programa almacenado de acceso aleatorio (RASP) es una máquina abstracta que se utiliza para el desarrollo de algoritmos y la teoría de la complejidad de los 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 (capacidad infinita); si el número de registros es finito es específico del modelo. Así, el RASP es para la RAM como la máquina de Turing universal es para 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 más cercano de todos los modelos abstractos 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 de los procesadores CISC e incluso RISC a las instrucciones aritméticas más simples, "movimientos" de registro a registro y "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 forma los cuatro modelos de máquina secuencial comunes , llamados así para distinguirlos de los modelos "paralelos" (por ejemplo , máquina paralela de acceso aleatorio ) [cf. van Emde Boas (1990)].
Definición informal: modelo de programa almacenado de acceso aleatorio (RASP)
Descripción resumida de un RASP:
- El RASP es una máquina de Turing universal (UTM) construida sobre un chasis RAM de máquina de acceso aleatorio.
El lector recordará que la UTM es una máquina de Turing con una tabla de instrucciones de estado finito "universal" que puede interpretar cualquier "programa" bien formado escrito en la cinta como una cadena de 5 tuplas de Turing, de ahí su universalidad. Si bien el modelo UTM clásico espera encontrar 5 tuplas de Turing en su cinta, cualquier conjunto de programas imaginable se puede colocar allí dado que la máquina de Turing espera encontrarlas, dado que su tabla de estados finitos puede interpretarlas y convertirlas a la acción deseada. Junto con el programa, impresos en la cinta estarán los datos / parámetros / números de entrada (generalmente a la derecha del programa), y eventualmente los datos / números de salida (generalmente 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 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 huecos (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 estado (el "intérprete") y el "programa" en los huecos. No es necesario que los dos conjuntos se extraigan del mismo conjunto.
Un ejemplo de RAM que funciona como RASP
El siguiente ejemplo de un programa moverá el contenido del registro (hoyo) # 18 al registro (hoyo) # 19, borrando el contenido del # 18 en el proceso.
5: 03 18 15 JZ 18 , 15 ; si [18] es cero, salte a 15 para finalizar el programa 02 18 DIC 18 ; Decreto [18] 01 19 INC 19 ; Incremento [19] 03 15 05 JZ 15 , 5 ; Si [15] es cero, salto a 5 para repetir el bucle (uso Halt a salto incondicional Simular) 15: 00 H ; Detener 18: n ; Valor de fuente para copiar 19 :; Destino de la copia
Las instrucciones del programa disponibles en esta máquina RASP serán un conjunto simple para que el ejemplo sea breve:
Instrucción | Mnemotécnico | Acción sobre el registro "r" | Acción en el registro de instrucciones de la máquina de estados finitos, IR |
---|---|---|---|
Incremento | INC (r) | [r] +1 → r | [IR] +1 → IR |
Decremento | DEC (r) | [r] -1 → r | [IR] +1 → IR |
Saltar si es cero | JZ (r, z) | ninguno | SI [r] = 0 ENTONCES z → IR ELSE [IR] +1 → IR |
Detener | H | ninguno | [IR] → IR |
Para facilitar el ejemplo, equiparemos la máquina de estado de RAM-as-RASP con las instrucciones primitivas extraídas del mismo conjunto, pero aumentadas con dos instrucciones de copia indirectas:
- Instrucciones de la máquina de estado RAM:
- { Pulgada; DEC h; JZ h, xxx; CPY «h una », ⟨h un ⟩; CPY ⟨h un ⟩, «h una »}
A medida que la máquina de estado de la máquina RASP interpreta el programa en los registros, ¿qué hará exactamente la máquina de estado? ¡La columna que contiene el signo de exclamación! enumerará en secuencia de tiempo las acciones de la máquina de estado a medida que "interpreta" - convierte en acción - el programa:
ordenador personal | IR | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
agujero # → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | dieciséis | 17 | 18 | 19 |
programa, parámetros → | 5 | JZ | 18 | 15 | DIC | 18 | C ª | 19 | JZ | 15 | 5 | H | norte | ||||||
programa codificado → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | ||||||
instrucciones de la máquina de estado ↓ | |||||||||||||||||||
! |
La tradición divide las acciones de la máquina de estado en dos "fases" principales llamadas Buscar y Ejecutar . Observaremos a continuación que hay "subfases" dentro de estas dos fases principales. No hay una convención acordada; cada modelo requerirá su propia descripción precisa.
Fase de búsqueda
La máquina de estado tiene acceso a todos los registros, tanto directa como indirectamente. Por lo tanto, adopta el número 1 como PC "contador de programas". La función del contador del programa será "mantener el lugar" en la lista del programa; la máquina estatal tiene su propio registro estatal para su uso privado.
Al iniciarse, la máquina de estado espera encontrar un número en la PC, la primera "Instrucción de programa" en el programa (es decir, en el número 5).
(Sin el uso de las COPY indirectas, la tarea de llevar la instrucción de programa apuntada a # 2 es un poco ardua. La máquina de estado disminuiría indirectamente el registro apuntado mientras incrementa directamente el registro # 2 (vacío). la fase de "análisis" restaurará el contenido sacrificado del n. ° 5 sacrificando el recuento del n. ° 2).
El objetivo del desvío anterior es mostrar que la vida es mucho más fácil cuando la máquina de estado tiene acceso a dos tipos de copia indirecta:
- copiar indirecta desde i y dirigir a j: CPY «h i », ⟨h j ⟩
- copia directa desde i e indirecta a j: CPY ⟨h i ⟩, «h j »
El siguiente ejemplo muestra lo que sucede durante la fase de "búsqueda" de la máquina de estado. Las operaciones de la máquina de estado se enumeran en la columna denominada "Instrucción de la máquina de estado ↓". Observe que al final de la búsqueda, el registro # 2 contiene el valor numérico 3 del "código de operación" ("código de operación") de la primera instrucción JZ :
ordenador personal | PIR | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
agujero # → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | dieciséis | 17 | 18 | 19 | ||
programa, parámetros → | 5 | JZ | 18 | 15 | DIC | 18 | C ª | 19 | JZ | 15 | 5 | H | norte | ||||||||
programa codificado → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | ||||||||
paso | instrucciones de la máquina de estado ↓ | ||||||||||||||||||||
1 | fetch_instr: | CPY ⟪1⟫, ⟨2⟩ | 5 yo | [3] | [3] | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte |
Fase de análisis
Ahora que el número de la instrucción de programa (por ejemplo, 3 = "JZ") está en el registro # 2, el PIR "Registro de instrucción de programa", la máquina de estado procede a disminuir el número hasta que el IR está vacío:
Si el IR estuviera vacío antes del decremento, entonces la instrucción de 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 "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 DETENERSE (por ejemplo).
ordenador personal | IR | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
agujero # → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | dieciséis | 17 | 18 | 19 | ||
programa, parámetros → | 5 | JZ | 18 | 15 | DIC | 18 | C ª | 19 | JZ | 15 | 5 | H | norte | ||||||||
programa codificado → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | ||||||||
instrucciones de la máquina de estado ↓ | |||||||||||||||||||||
CPY ⟪1⟫, ⟨2⟩ | 5 yo | [3] | [3] | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | |||||||
JZ 2, detener | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | norte | |||||||
3 | 2 DE DICIEMBRE | 5 | 2 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | ||||||
4 | JZ 2, inc_rutina: | 5 | 2 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | ||||||
5 | 2 DE DICIEMBRE | 5 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | ||||||
6 | JZ 2, dec_routine | 5 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | ||||||
7 | 2 DE DICIEMBRE | 5 | 0 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | ||||||
8 | JZ 2, JZ_rutina | 5 | 0! | ||||||||||||||||||
- | detener: | DETENER | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | |||||
- | inc_routine: | etc. | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | |||||
- | dec_routine: | etc. | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | |||||
9 | JZ_routine: | etc. | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte |
Fase de ejecución, JZ_routine
Ahora la máquina de estado sabe qué instrucción de programa ejecutar; de hecho, ha saltado a la secuencia de instrucciones "JZ_routine". La instrucción JZ tiene 2 operandos: (i) el número del registro para probar y (ii) la dirección a la que ir si la prueba es exitosa (el agujero está vacío).
(i) Búsqueda de operandos: ¿qué registro probar si está vacío? : De forma análoga a la fase de búsqueda, la máquina de estado finito 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 usa el contenido del registro # 2 para señalar el registro que se va a probar para cero, es decir, el registro # 18. El hoyo # 18 contiene un número "n". Para hacer la prueba, ahora la máquina de estado usa el contenido del PIR para copiar indirectamente el contenido del registro # 18 en un registro de repuesto, # 3. Entonces hay dos eventualidades (ia), el registro # 18 está vacío, (ib) el registro # 18 no está vacío.
(ia): Si el registro n. ° 3 está vacío, la máquina de estado 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 estado puede omitir (ii) la búsqueda del segundo operando. Simplemente incrementa dos veces la PC y luego regresa incondicionalmente a la fase de búsqueda de instrucciones, donde obtiene la instrucción de programa # 8 (DEC).
(ii) Búsqueda de operando: dirección de salto . Si el registro # 3 está vacío, la máquina de estado procede a usar la PC para copiar indirectamente el contenido del registro al que apunta (# 8) en sí mismo . Ahora la PC tiene la dirección de salto 15. Luego, la máquina de estado regresa incondicionalmente a la fase de búsqueda de instrucciones, donde obtiene la instrucción de programa # 15 (HALT).
ordenador personal | IR | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
agujero # → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | dieciséis | 17 | 18 | 19 | ||
programa, parámetros → | 5 | JZ | 18 | 15 | DIC | 18 | C ª | 19 | JZ | 15 | 5 | H | norte | ||||||||
programa codificado → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | ||||||||
paso | instrucciones de la máquina de estado ↓ | ||||||||||||||||||||
9 | JZ_routine | INC 1 | [6] | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | |||||
10 | CPY ⟪1⟫, ⟨2⟩ | 6 yo | [18] | 3 | [18] | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | ||||||
11 | agujero de prueba: | CPY ⟪2⟫, ⟨3⟩ | 6 | 18 yo | [norte] | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | [norte] | ||||
12 | agujero de prueba: | JZ 3, saltar | 6 | 18 yo | [norte] | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | ||||
norte | norte | ||||||||||||||||||||
13 | no_jump: | INC 1 | [7] | 18 | norte | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | ||||
14 | INC 1 | [8] | 18 | norte | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | |||||
15 | J fetch_instr | 8 | 18 | norte | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | |||||
1 | fetch_instr: | CPY ⟪1⟫, ⟨2⟩ | 8 yo | [2] | norte | 3 | 18 | 15 | [2] | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | ||||
2 | analizar gramaticalmente: | etc. | |||||||||||||||||||
13 | saltar: | INC 1 | [7] | 18 | norte | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | ||||
14 | CPY ⟪1⟫, ⟨1⟩ | [15] | 18 | norte | 3 | 18 | [15] | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | |||||
15 | J fetch_instr | 15 | 18 | norte | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | |||||
1 | fetch_instr: | CPY ⟪1⟫, ⟨2⟩ | 15 yo | [0] | norte | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | [0] | norte | ||||
2 | analizar gramaticalmente: | etc. |
Ejecutar fase INC, DEC
Lo siguiente completa la interpretación de la máquina de estado 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 "suplantar" un RASP:
- Conjunto de instrucciones del programa de destino: {INC h; DEC h; JZ h, xxx, HALT}
Sin indirectos instrucciones de máquina de estados INCI y Deci, para ejecutar las INC y DEC programa -Instrucciones la máquina de estados debe utilizar la copia indirecta para obtener el contenido de la cual apunta a registrar en el registro repuesto # 3, DEC o INC, y luego su uso copia indirecta para enviarlo de vuelta al registro apuntado.
ordenador personal | IR | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
agujero # → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | dieciséis | 17 | 18 | 19 | ||
programa, parámetros → | 5 | JZ | 18 | 15 | DIC | 18 | C ª | 19 | JZ | 15 | 5 | H | norte | ||||||||
programa codificado → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | ||||||||
instrucciones de la máquina de estado ↓ | |||||||||||||||||||||
15 | J fetch_instr | 8 | 18 | norte | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | |||||
dieciséis | fetch_instr: | CPY ⟪1⟫, ⟨2⟩ | 8 yo | [2] | norte | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | ||||
17 | analizar gramaticalmente: | JZ 2, detener | 8 | 2 | norte | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | ||||
18 | 2 DE DICIEMBRE | 8 | [1] | norte | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | |||||
19 | JZ 2, inc_rutina: | 8 | 1 | norte | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | |||||
20 | 2 DE DICIEMBRE | 8 | [0] | norte | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | |||||
21 | JZ 2, dec_routine: | 8 | 0! | norte | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | |||||
22 | dec_routine: | INC 1 | 9 | 0 | norte | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | ||||
23 | CPY ⟪1⟫, ⟨2⟩ | 9 yo | 18 | norte | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | |||||
24 | CPY ⟪2⟫, ⟨3⟩ | 9 | 18 yo | norte | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | |||||
25 | JZ 3, * + 2 | 9 | 18 | norte | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | |||||
26 | 3 DE DICIEMBRE | 9 | 18 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | norte | |||||
27 | CPY ⟨3⟩, ⟪2⟫ | 9 | 18 yo | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | |||||
28 | INC 1 | 10 | 18 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | |||||
29 | J fetch_instr | 10 | 18 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | |||||
30 | fetch_instr: | CPY ⟪1⟫, ⟨2⟩ | 10 i | 1 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | ||||
31 | analizar gramaticalmente: | JZ 2, detener | 10 | 1 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | ||||
32 | 2 DE DICIEMBRE | 10 | 0 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | |||||
33 | JZ 2, inc_rutina: | 10 | 0! | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | |||||
34 | inc_routine: | INC 1 | 11 | 0 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | ||||
35 | CPY ⟪1⟫, ⟨2⟩ | 11 yo | 19 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | |||||
36 | CPY ⟪2⟫, ⟨3⟩ | 11 | 19 i | 0 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | 0 | ||||
37 | INC 3 | 11 | 19 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | 0 | ||||
38 | CPY ⟨3⟩, ⟪2⟫ | 11 | 19 i | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | 1 | ||||
39 | INC 1 | 12 | 19 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | 0 | ||||
40 | J fetch_instr | 12 | 19 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | 0 | ||||
41 | fetch_instr: | etc. | 12 | 19 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | 0 |
Instrucciones alternativas : Aunque la manifestación dio lugar a una escofina primitiva de sólo cuatro instrucciones, el lector puede imaginar como una instrucción adicional como "ADD ⟨h⟩" o "MULT ⟨h un ⟩, «h b > podría hacerse.
Programas RASP auto modificables
Cuando una RAM actúa como un RASP, se ha ganado algo nuevo: a diferencia de la RAM, el RASP tiene la capacidad de auto-modificar sus instrucciones de programa (las instrucciones de la máquina de estado están congeladas, no modificables por la máquina). Cook-Reckhow (1971) (p. 75) comentan sobre 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):
- "Necesitamos un orden [instrucción] que pueda sustituir un número en un orden dado ... Por medio de dicho orden, los resultados de un cálculo pueden introducirse en las instrucciones que gobiernan ese o un cálculo diferente" (p. 93)
Tal habilidad hace posible lo siguiente:
- subrutinas : la rutina de llamada (o quizás la subrutina) almacena la dirección de retorno "return_address" en el último comando de la subrutina, es decir, "JMP return_address"
- las llamadas tablas JUMP
- código auto modificable
Conjunto de instrucciones de programa RASP de Cook y Reckhow (1973)
En un artículo influyente, Stephen A. Cook y Robert A. Reckhow definen su versión de un RASP:
- "La máquina de programa almacenado de acceso aleatorio (RASP) descrita aquí es similar a la RASP descrita por Hartmanis [1971]" (p. 74).
Su propósito era comparar los tiempos de ejecución de los distintos modelos: RAM, RASP y máquina de Turing de múltiples cintas para su uso en la teoría del análisis de complejidad .
La característica más destacada de su modelo RASP es que no se prevén instrucciones de programa indirectas (véase su discusión en la p. 75). Esto lo logran requiriendo 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 para 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 son ilimitados en capacidad y ilimitados en número; del mismo modo, su AC acumulador y el contador de instrucciones IC son ilimitados. El conjunto de instrucciones es el siguiente:
operación | mnemotécnico | código de operación | descripción |
---|---|---|---|
carga constante | LOD, k | 1 | poner constante k en el acumulador |
agregar | AÑADIR, j | 2 | agregar el contenido del registro j al acumulador |
sustraer | SUB, j | 3 | restar el contenido del registro j del acumulador |
Tienda | STO, j | 4 | copiar el contenido del acumulador en el registro j |
rama en acumulador positivo | BPA, xxx | 5 | SI el contenido del acumulador> 0 ENTONCES salta a xxx ELSE siguiente instrucción |
leer | RD, j | 6 | siguiente entrada en el registro j |
impresión | PRI, j | 7 | contenido de salida del registro j |
detener | HLT | cualquier otro - o + entero | detener |
Referencias
A menudo, las máquinas RAM y RASP se presentan juntas en el mismo artículo. Estos se han copiado de una máquina de acceso aleatorio ; con algunas excepciones, estas referencias son las mismas que las de la máquina de registro .
- George Boolos , John P. Burgess , Richard Jeffrey (2002), Computabilidad y lógica: Cuarta edición , Cambridge University Press, Cambridge, Inglaterra. El texto original de Boolos-Jeffrey ha sido revisado extensamente por Burgess: más avanzado que un libro de texto introductorio. El modelo de "máquina de ábaco" se desarrolla extensamente en el Capítulo 5 Computabilidad del ábaco ; es uno de los tres modelos tratados y comparados extensamente: la máquina de Turing (todavía en la forma original de 4 tuplas de Boolos) y la recursividad los otros dos.
- Arthur Burks , Herman Goldstine , John von Neumann (1946), Discusión preliminar del diseño lógico de un instrumento informático electrónico , reimpreso pp. 92ff en Gordon Bell y Allen Newell (1971), Computer Structures: Readings and Examples , mc Graw-Hill Book Company, Nueva York. ISBN 0-07-004357-4 .
- Stephen A. Cook y Robert A. Reckhow (1972), Máquinas de acceso aleatorio limitadas en el tiempo , Journal of Computer Systems Science 7 (1973), 354-375.
- Martin Davis (1958), Computability & Unsolvability , McGraw-Hill Book Company, Inc. Nueva York.
- Calvin Elgot y Abraham Robinson (1964), Máquinas de programa almacenado de acceso aleatorio, una aproximación a los lenguajes de programación , Revista de la Asociación de Maquinaria de Computación, vol. 11, núm. 4 (octubre de 1964), págs. 365–399.
- J. Hartmanis (1971), "Complejidad computacional de las máquinas de programas almacenados de acceso aleatorio", Teoría de sistemas matemáticos 5, 3 (1971) págs. 232–245.
- John Hopcroft , Jeffrey Ullman (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas , 1ª ed., Reading Mass: Addison-Wesley. ISBN 0-201-02988-X . Un libro difícil centrado en los problemas de la interpretación automática de "lenguajes", NP-Completeness, etc.
- Stephen Kleene (1952), Introducción a las metamatemáticas , North-Holland Publishing Company, Amsterdam, Países Bajos. ISBN 0-7204-2103-9 .
- Donald Knuth (1968), El arte de la programación informática , segunda edición 1973, Addison-Wesley, Reading, Massachusetts. Cf. páginas 462-463 donde define "un nuevo tipo de máquina abstracta o 'autómata' que se ocupa de estructuras enlazadas".
- Joachim Lambek (1961, recibido el 15 de junio de 1961), Cómo programar un ábaco infinito , Boletín matemático, vol. 4, no. 3. Septiembre de 1961 páginas 295-302. En su Apéndice II, Lambek propone una "definición formal de 'programa'. Hace referencia a Melzak (1961) y Kleene (1952) Introducción a las metamatemáticas .
- ZA Melzak (1961, recibido el 15 de mayo de 1961), Un enfoque aritmético informal a la computabilidad y la computación , Canadian Mathematical Bulletin, vol. 4, no. 3. Septiembre de 1961 páginas 279-293. Melzak no ofrece referencias, pero reconoce "el beneficio de las conversaciones con los doctores R. Hamming, D. McIlroy y V. Vyssots de los Bell Telephone Laborators y con el Dr. H. Wang de la Universidad de Oxford".
- Marvin Minsky (1961, recibido el 15 de agosto de 1960). "Inestabilidad recursiva del problema de Post de 'etiqueta' y otros temas en la teoría de las máquinas de Turing". Annals of Mathematics . Annals of Mathematics. 74 (3): 437–455. doi : 10.2307 / 1970290 . JSTOR 1970290 . Verifique los valores de fecha en:
|date=
( ayuda ) - Marvin Minsky (1967). Computación: máquinas finitas e infinitas (1ª ed.). Englewood Cliffs, Nueva Jersey: Prentice-Hall, Inc. ISBN 0-13-165449-7.En particular, consulte el capítulo 11: Modelos similares a las computadoras digitales y el capítulo 14: Bases muy simples para la computabilidad . En el capítulo anterior define "Máquinas de programa" y en el capítulo posterior analiza "Máquinas de programa universal con dos registros" y "... con un registro", etc.
- John C. Shepherdson y HE Sturgis (1961) recibieron en diciembre de 1961 Computability of Recursive Functions , Journal of the Association of Computing Machinery (JACM) 10: 217-255, 1963. Un artículo de referencia extremadamente valioso. En su Apéndice A, los autores citan otros 4 con referencia a "Mínimo de instrucciones utilizadas en 4.1: Comparación con sistemas similares".
- Kaphengst, Heinz, Eine Abstrakte programmgesteuerte Rechenmaschine ' , Zeitschrift fürhematische Logik und Grundlagen der Mathematik: 5 (1959), 366-379.
- Ershov, AP Sobre algoritmos de operador , (ruso) Dok. Akad. Nauk 122 (1958), 967-970. Traducción al inglés, Automat. Express 1 (1959), 20-23.
- Péter, Rózsa Graphschemata und rekursive Funktionen , Dialectica 12 (1958), 373.
- Hermes, Hans Die Universalität programmgesteuerter Rechenmaschinen. Math.-Phys. Semsterberichte (Gotinga) 4 (1954), 42-53.
- Arnold Schönhage (1980), Máquinas de modificación de almacenamiento , Sociedad de Matemáticas Industriales y Aplicadas, SIAM J. Comput. Vol. 9, No. 3, agosto de 1980. Donde Schōnhage muestra la equivalencia de su SMM con el "sucesor RAM" (Random Access Machine), etc. resp. Storage Modification Machines , en Theoretical Computer Science (1979), págs. 36-37
- Peter van Emde Boas , Machine Models and Simulations págs. 3-66, que aparece en: Jan van Leeuwen , ed. "Manual de Ciencias de la Computación Teóricas. Volumen A: Algoritmos y Complejidad , The MIT PRESS / Elsevier, 1990. ISBN 0-444-88071-2 (volumen A). QA 76.H279 1990.
- El tratamiento de van Emde Boas de los SMM aparece en las págs. 32-35. Este tratamiento aclara Schōnhage 1980: sigue de cerca pero amplía ligeramente el tratamiento de Schōnhage. Es posible que se necesiten ambas referencias para una comprensión eficaz.
- Hao Wang (1957), una variante de la teoría de las máquinas informáticas de Turing , JACM (Revista de la Asociación de Maquinaria Informática) 4; 63-92. Presentado en la reunión de la Asociación, 23-25 de junio de 1954.