Máquina de programas almacenados de acceso aleatorio

En la informática teórica, el modelo de máquina de programa almacenado de acceso aleatorio (RASP, por sus siglas en inglés) es una máquina abstracta que se utiliza para el desarrollo de algoritmos y la teoría de la complejidad algorítmica .

La RASP es un modelo de máquina de acceso aleatorio (RAM) que, a diferencia de la RAM, almacena su programa en sus "registros" junto con su entrada. Los registros son ilimitados (de capacidad infinita); si el número de registros es finito depende del modelo. Así, la RASP es a la RAM lo que la máquina de Turing universal es a la máquina de Turing . La 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 suele tener un conjunto de instrucciones muy simple, muy reducido en comparación con los procesadores CISC e incluso RISC , limitándose a las operaciones aritméticas más básicas, movimientos de registro a registro e instrucciones de prueba/salto. Algunos modelos incluyen algunos registros adicionales, como un acumulador .

Junto con la máquina de registros , la RAM y la máquina de punteros , la RASP conforma los cuatro modelos comunes de máquinas secuenciales , llamados así para distinguirlos de los modelos "paralelos" (por ejemplo, máquina de acceso aleatorio paralela ) [cf. van Emde Boas (1990)].

Definición informal: modelo de programa almacenado de acceso aleatorio (RASP)

Descripción concisa de un RASP:

La RASP es una máquina de Turing universal (UTM) construida sobre un chasis de memoria RAM de acceso aleatorio .

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. Si bien el modelo clásico de la UTM espera encontrar 5-tuplas de Turing en su cinta, se puede colocar allí cualquier conjunto de programas imaginable, siempre que la máquina de Turing espere 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 (generalmente a la derecha del programa) y, finalmente, los datos/números de salida (generalmente a la derecha de ambos, o mezclados con la entrada, o reemplazándola). El "usuario" debe colocar el cabezal de la máquina de Turing sobre la primera instrucción, y la entrada debe colocarse en un lugar y formato específicos, apropiados tanto para el programa en cinta como para la tabla de instrucciones de la máquina de estados finitos .

El RASP imita esta estructura: coloca el "programa" y los "datos" en los huecos (registros). Pero a diferencia del UTM, el RASP procede a "obtener" sus instrucciones de forma secuencial, a menos que la condición indique lo contrario.

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 huecos. Los dos conjuntos no tienen por qué provenir del mismo conjunto.

Un ejemplo de una RAM funcionando como una RASP

El siguiente ejemplo de programa moverá el contenido del registro (hueco) n.° 18 al registro (hueco) n.° 19, borrando el contenido del n.° 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 Halt para simular un salto incondicional) 15: 00 H ; Halt18: n ; Valor de origen a copiar 19: ; Destino para la copia

Las instrucciones del programa disponibles en esta máquina RASP serán un conjunto sencillo para que el ejemplo sea breve:

Para simplificar el ejemplo, equiparemos la máquina de estados de la RAM-as-RASP con las instrucciones primitivas extraídas del mismo conjunto, pero aumentadas con dos instrucciones de copia indirecta:

Instrucciones de la máquina de estados de la RAM:

{ INC h; DEC h; JZ h,xxx; CPY ⟪h _a ⟫, ⟨ h _a⟩ ; CPY ⟨ h _a⟩ ,⟪h _a ⟫ }

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 orden cronológico las acciones de la máquina de estados a medida que "interpreta" —convierte en acción— el programa:

Tradicionalmente, las acciones de la máquina de estados se dividen en dos fases principales: Captura y Ejecución . Como veremos más adelante, existen subfases dentro de estas dos fases principales. No existe una convención universalmente aceptada; cada modelo requerirá su propia descripción precisa.

Fase de recuperación

La máquina de estados tiene acceso a todos los registros, tanto de forma directa como indirecta. Por lo tanto, adopta el registro n.° 1 como contador de programa (PC). La función del contador de programa es mantener la posición en la lista del programa; la máquina de estados dispone de su propio registro de estado para uso exclusivo.

Al iniciarse, la máquina de estados espera encontrar un número en el PC: la primera "Instrucción de programa" del programa (es decir, en el número 5).

(Sin el uso de las COPIAS indirectas, la tarea de introducir la instrucción del programa apuntada en el registro n.° 2 resulta algo ardua. La máquina de estados decrementaría indirectamente el registro apuntado mientras incrementa directamente el registro n.° 2 (vacío). Durante la fase de "análisis", restaurará el contenido sacrificado del registro n.° 5 sacrificando el contador del registro n.° 2).

El objetivo de la digresión anterior es demostrar que la vida es mucho más fácil cuando la máquina de estados tiene acceso a dos tipos de copia indirecta:

Copia indirecta de i y directa a j: CPY ⟪h _i ⟫, ⟨ h _j⟩
Copiar directamente de i e indirectamente a j: CPY ⟨ h _i⟩ ,⟪h _j ⟫

El siguiente ejemplo muestra lo que sucede durante la fase de "captura" de la máquina de estados. Las operaciones de la máquina de estados se enumeran en la columna etiquetada como "Instrucción de la máquina de estados ↓". Observe que al final de la captura, el registro n.° 2 contiene el valor numérico 3 del "código de operación" (" opcode ") de la primera instrucción JZ :

Fase de análisis

Ahora que el número de la instrucción del programa (por ejemplo, 3 = "JZ") está en el registro n.° 2, el registro PIR ("Registro de Instrucción del Programa"), 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, 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 hueco 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 rutina "dec_routine". Después del tercer decremento, el IR está efectivamente vacío, y esto provoca un salto a la rutina "JZ_routine". Si aún hubiera un número inesperado en el IR, la máquina habría detectado un error y podría detenerse (por ejemplo).

Fase de ejecución, rutina JZ

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 a comprobar y (ii) la dirección a la que se debe ir si la comprobación es exitosa (el hueco está vacío).

(i) Captura de operando : ¿qué registro comprobar si está vacío? : De forma análoga a la fase de captura, la máquina de estados finitos mueve el contenido del registro al que apunta el PC, es decir, el hueco n.º 6, al registro de instrucciones de programa (PIR) n.º 2. A continuación, utiliza el contenido del registro n.º 2 para apuntar al registro que se va a comprobar si es cero, es decir, el registro n.º 18. El hueco n.º 18 contiene un número "n". Para realizar la comprobación, la máquina de estados utiliza el contenido del PIR para copiar indirectamente el contenido del registro n.º 18 en un registro de reserva, 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) Obtención del segundo operando : obtener la dirección de salto.

(ib): Si el registro #3 no está vacío, la máquina de estados puede omitir (ii) la búsqueda del segundo operando. Simplemente incrementa el PC dos veces y luego regresa incondicionalmente a la fase de búsqueda de instrucciones, donde busca la instrucción de programa #8 (DEC).

(ii) Captura de operando : dirección de salto . Si el registro n.° 3 está vacío, la máquina de estados procede a usar el PC para copiar indirectamente el contenido del registro al que apunta (n.° 8) en sí mismo . Ahora el PC contiene la dirección de salto 15. Luego, la máquina de estados regresa incondicionalmente a la fase de captura de instrucciones, donde captura la instrucción de programa n.° 15 (HALT).

Ejecutar fase INC, DEC

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 "suplantar" una RASP:

Conjunto de instrucciones del programa objetivo: { INC h; DEC h; JZ h,xxx, HALT }

Sin las instrucciones indirectas de la máquina de estados INCi y DECi, para ejecutar las instrucciones del programa INC y DEC , la máquina de estados debe usar la copia indirecta para obtener el contenido del registro al que apunta en el registro de reserva n.° 3, DEC o INC en él, y luego usar la copia indirecta para enviarlo de vuelta al registro al que apunta.

Instrucciones alternativas : Aunque la demostración dio como resultado un RASP primitivo de solo cuatro instrucciones, el lector podría imaginar cómo se podría hacer una instrucción adicional como "ADD ⟨ h ⟩ " o "MULT ⟨ h _a⟩ ,⟪h _{b >.}

Programas RASP auto-modificables

Cuando una RAM actúa como una RASP, se obtiene una ventaja: a diferencia de la RAM, la RASP tiene la capacidad de automodificar sus instrucciones de programa (las instrucciones de la máquina de estados están congeladas y no pueden ser modificadas por la máquina). Cook-Reckhow (1971) (p. 75) comentan esto en su descripción del modelo RASP, al igual que Hartmanis (1971) (pp. 239 y ss.).

Una descripción temprana de esta noción se puede encontrar en Goldstine-von Neumann (1946):

"Necesitamos una orden [instrucción] que pueda sustituir un número en una orden dada... Mediante dicha orden, los resultados de un cálculo pueden introducirse en las instrucciones que rigen ese u otro cálculo" (p. 93).

Esta capacidad hace posible lo siguiente:

subrutinas : la rutina que realiza la 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 automodificable

Conjunto de instrucciones del programa RASP de Cook y Reckhow (1973)

En un influyente artículo, Stephen A. Cook y Robert A. Reckhow definen su versión de un RASP:

"La máquina de programas almacenados de acceso aleatorio (RASP) descrita aquí es similar a las RASP descritas 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 la complejidad .

La característica más destacada de su modelo RASP es la ausencia de instrucciones de programa indirectas (véase su análisis en la página 75). Esto lo logran exigiendo que el programa se modifique a sí mismo: si es necesario, una instrucción puede modificar el "parámetro" (término que ellos utilizan, es decir, el "operando") de una instrucción específica. Han diseñado su modelo de manera que cada "instrucción" utilice dos registros consecutivos: uno para el "código de operación" (término que ellos utilizan) y otro para el parámetro, que puede ser una dirección o una constante entera.

Los registros de su RASP no tienen límite de capacidad ni de número; asimismo, su acumulador AC y su contador de instrucciones IC tampoco tienen límite. El conjunto de instrucciones es el siguiente:

Referencias

A menudo, tanto la máquina RAM como la RASP se presentan juntas en el mismo artículo. Estas se han copiado de Máquina de acceso aleatorio ; con algunas excepciones, estas referencias son las mismas que las de 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 y Jeffrey ha sido revisado exhaustivamente por Burgess: más avanzado que un libro de texto introductorio. El modelo de la "máquina de ábaco" se desarrolla ampliamente en el Capítulo 5, Computabilidad con ábaco ; es uno de los tres modelos tratados y comparados en profundidad: la máquina de Turing (aún en la forma original de 4-tuplas de Boolos) y dos modelos de recursión.
Arthur Burks , Herman Goldstine , John von Neumann (1946), Discusión preliminar sobre el diseño lógico de un instrumento de computación electrónica , reimpreso en las páginas 92 y siguientes en Gordon Bell y Allen Newell (1971), Estructuras de computadoras: lecturas y ejemplos , McGraw-Hill Book Company, Nueva York. ISBN 0-07-004357-4 .
Stephen A. Cook y Robert A. Reckhow (1972), Máquinas de acceso aleatorio con límite de tiempo , Journal of Computer Systems Science 7 (1973), 354–375.
Martin Davis (1958), Computabilidad e insolubilidad , McGraw-Hill Book Company, Inc. Nueva York.
Calvin Elgot y Abraham Robinson (1964), Máquinas de programas almacenados de acceso aleatorio, un enfoque a los lenguajes de programación , Journal of the Association for Computing Machinery, vol. 11, n.º 4 (octubre de 1964), págs. 365-399.
J. Hartmanis (1971), "Complejidad computacional de las máquinas de programas almacenados de acceso aleatorio", Mathematical Systems Theory 5, 3 (1971) pp. 232–245.
John Hopcroft , Jeffrey Ullman (1979). Introducción a la teoría de autómatas, lenguajes y computación , 1.ª ed., Reading, Mass.: Addison-Wesley. ISBN 0-201-02988-XUn libro complejo centrado en cuestiones como la interpretación automática de "lenguajes", la NP-completitud, etc.
Stephen Kleene (1952), Introducción a la metamatemática , North-Holland Publishing Company, Ámsterdam, 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. Véanse las páginas 462-463, donde define "un nuevo tipo de máquina abstracta o 'autómata' que trabaja con estructuras enlazadas".
Joachim Lambek (1961, recibido el 15 de junio de 1961), Cómo programar un ábaco infinito , Mathematical Bulletin, vol. 4, n.º 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 la metamatemática .
ZA Melzak (1961, recibido el 15 de mayo de 1961), Un enfoque aritmético informal de la computabilidad y la computación , Boletín Matemático Canadiense , vol. 4, n.º 3, septiembre de 1961, páginas 279-293. Melzak no ofrece referencias, pero reconoce "el beneficio de las conversaciones con los Dres. R. Hamming , D. McIlroy y V. Vyssotsky de los Laboratorios Bell Telephone y con el Dr. H. Wang de la Universidad de Oxford".
Marvin Minsky (1961). "Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines". Annals of Mathematics . 74 (3): 437– 455. doi : 10.2307/1970290 . JSTOR 1970290 .
Marvin Minsky (1967). Computación: Máquinas finitas e infinitas (1.ª ed.). Englewood Cliffs, NJ: Prentice-Hall, Inc. ISBN 0-13-165449-7.En particular, véanse los capítulos 11: Modelos similares a las computadoras digitales y 14: Bases muy simples para la computabilidad . En el primer capítulo define las "máquinas de programa" y en el segundo analiza las "máquinas de programa universales 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 for Computing Machinery (JACM) 10:217-255, 1963. Un artículo de referencia sumamente valioso. En su Apéndice A, los autores citan a otros 4 autores con referencia a "Minimality of Instructions Used in 4.1: Comparison with Similar Systems".

Kaphengst, Heinz, Eine Abstrakte programmgesteuerte Rechenmaschine' , Zeitschrift fur mathematische Logik und Grundlagen der Mathematik: 5 (1959), 366-379.
Ershov, AP Sobre algoritmos de operadores , (en 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 . Matemáticas-Física. Semsterberichte (Gotinga) 4 (1954), 42-53.

Arnold Schönhage (1980), Storage Modification Machines , Society for Industrial and Applied Mathematics, SIAM J. Comput. Vol. 9, No. 3, agosto de 1980. En el que Schönhage muestra la equivalencia de su SMM con la "RAM sucesora" (Random Access Machine), etc., respectivamente. Storage Modification Machines , en Theoretical Computer Science (1979), pp. 36–37.
Peter van Emde Boas , Machine Models and Simulations, págs. 3-66, publicado en: Jan van Leeuwen , ed. Handbook of Theoretical Computer Science. Volumen A: Algorithms and Complexity , The MIT PRESS/Elsevier, 1990. ISBN 0-444-88071-2(volumen A). QA 76.H279 1990.

El análisis de van Emde Boas sobre los SMM aparece en las páginas 32-35. Este análisis aclara el trabajo de Schōnhage (1980); lo sigue de cerca, pero lo amplía ligeramente. Ambas referencias pueden ser necesarias para una comprensión efectiva.

Hao Wang (1957), Una variante de la teoría de las máquinas de computación de Turing , JACM (Revista de la Asociación para la Maquinaria de Computación) 4; 63–92. Presentado en la reunión de la Asociación, del 23 al 25 de junio de 1954.