Máquina de acceso aleatorio

En informática , la máquina de acceso aleatorio ( RAM o RA ) es un modelo de computación que describe una máquina abstracta dentro de la clase general de máquinas de registro . La RA es muy similar a la máquina de contador , pero con la capacidad adicional de direccionamiento indirecto de sus registros. Los registros son intuitivamente equivalentes a la memoria principal de un ordenador común, con la diferencia de que pueden almacenar números naturales de cualquier tamaño. Al igual que la máquina de contador, la RA contiene las instrucciones de ejecución en la parte de estados finitos de la máquina (la denominada arquitectura Harvard ).

La máquina RA, equivalente a la máquina de Turing universal —con su programa y sus datos almacenados en los registros— , se denomina máquina de programa almacenado de acceso aleatorio o máquina RASP. Es un ejemplo de la arquitectura de von Neumann y se asemeja mucho a la concepción común de un ordenador .

Junto con los modelos de máquina de Turing y máquina contadora , los modelos de máquina RA y máquina RASP se utilizan para el análisis de la complejidad computacional . Van Emde Boas (1990) denomina a estos tres, junto con la máquina de punteros , modelos de "máquina secuencial", para distinguirlos de los modelos de " máquina de acceso aleatorio paralelo ".

Descripción informal

Una máquina RA consta de lo siguiente:

un número infinito de ubicaciones de memoria llamadas " registros "; cada registro tiene una dirección que es un número natural o cero; cada registro puede almacenar exactamente un número natural de cualquier tamaño, o un cero.
La tabla de instrucciones , o simplemente "tabla", contiene instrucciones de ejecución; el conjunto exacto de instrucciones varía según el autor; las instrucciones comunes incluyen: incremento, decremento, puesta a cero, copia, salto condicional, parada; otras instrucciones son innecesarias porque se pueden crear mediante combinaciones de instrucciones del conjunto de instrucciones.
un registro especial llamado " registro de instrucciones " (IR); este registro apunta a la instrucción que se está ejecutando en la tabla de instrucciones.

Para una descripción de un concepto similar, pero humorístico, véase el lenguaje de programación esotérico Brainfuck . ^{[ 1 ]}

Introducción al modelo

El concepto de máquina de acceso aleatorio (RAM) parte del modelo más simple de todos, el llamado modelo de máquina de contador . Sin embargo, dos modificaciones lo alejan de este modelo. La primera mejora la máquina con la conveniencia del direccionamiento indirecto; la segunda acerca el modelo a la computadora más convencional basada en acumulador, mediante la adición de uno o más registros auxiliares (dedicados), el más común de los cuales se denomina "acumulador".

Definición formal

Una máquina de acceso aleatorio (RAM) es un modelo abstracto de máquina computacional idéntico a una máquina contadora de múltiples registros, con la adición de direccionamiento indirecto. A discreción de la instrucción de su tabla de máquina de estados finitos , la máquina obtiene la dirección de un registro "objetivo" (i) directamente de la instrucción misma, o (ii) indirectamente del contenido (por ejemplo, número, etiqueta) del registro "puntero" especificado en la instrucción.

Por definición: Un registro es una ubicación con una dirección (una designación/localizador único y distinguible equivalente a un número natural) y un contenido : un único número natural. Para mayor precisión, utilizaremos la simbología cuasi formal de Boolos-Burgess-Jeffrey (2002) para especificar un registro, su contenido y una operación sobre él:

[r] significa "el contenido del registro con dirección r". La etiqueta "r" aquí es una "variable" que puede rellenarse con un número natural, una letra (por ejemplo, "A") o un nombre.
→ significa "copiar/depositar en" o "reemplazar", pero sin destruir la fuente.

Ejemplo: [3] + 1 → 3; significa "El contenido del registro de origen con dirección "3", más 1, se coloca en el registro de destino con dirección "3" (aquí origen y destino son el mismo lugar). Si [3] = 37, es decir, el contenido del registro 3 es el número "37", entonces 37 + 1 = 38 se colocará en el registro 3.

Ejemplo: [3] → 5; significa "El contenido del registro de origen con dirección "3" se coloca en el registro de destino con dirección "5". Si [3]=38, es decir, el contenido del registro 3 es el número 38, entonces este número se colocará en el registro 5. El contenido del registro 3 no se ve afectado por esta operación, por lo que [3] sigue siendo 38, ahora igual que [5].

Definición: Una instrucción directa especifica en sí misma la dirección del registro de origen o destino cuyo contenido será objeto de la instrucción. Definición: Una instrucción indirecta especifica un registro puntero, cuyo contenido es la dirección de un registro de destino. El registro de destino puede ser de origen o de destino (las instrucciones COPY proporcionan ejemplos de esto). Un registro puede direccionarse a sí mismo indirectamente.

A falta de un estándar/convención, este artículo especificará "directo/indirecto", abreviado como "d/i", como un parámetro (o parámetros) en la instrucción:

Ejemplo: COPY ( d , A, i , N ) significa que d obtiene directamente la dirección del registro de origen (registro "A") de la propia instrucción, pero indirectamente i obtiene la dirección de destino del registro puntero N. Supongamos que [N]=3, entonces el registro 3 es el destino y la instrucción hará lo siguiente: [A] → 3.

Definición: El contenido del registro fuente es utilizado por la instrucción. La dirección del registro fuente puede especificarse (i) directamente por la instrucción o (ii) indirectamente por el registro puntero especificado por la instrucción.

Definición: El contenido del registro puntero es la dirección del registro "destino".

Definición: El contenido del registro puntero apunta al registro de destino ; el "destino" puede ser un registro de origen o un registro de destino.

Definición: El registro de destino es donde la instrucción deposita su resultado. La dirección del registro de origen puede especificarse (i) directamente mediante la instrucción o (ii) indirectamente mediante el registro puntero especificado por la instrucción. Los registros de origen y destino pueden ser el mismo.

Repaso: El modelo de máquina de mostrador

Melzak (1961) ofrece una representación visual sencilla de una máquina contadora: sus "registros" son agujeros en el suelo que contienen guijarros. Siguiendo una instrucción, la "computadora" (persona o máquina) añade (incrementa) o retira (decrementa) un guijarro de estos agujeros. Según sea necesario, se obtienen guijarros adicionales de un suministro infinito y los sobrantes se devuelven a él; si el agujero es demasiado pequeño para los guijarros, la "computadora" lo agranda.

Minsky (1961) y Hopcroft-Ullman (1979, p. 171) ofrecen la visualización de una máquina de Turing de múltiples cintas con tantas cintas con extremo izquierdo como "registros". La longitud de cada cinta es ilimitada hacia la derecha, y cada casilla está en blanco excepto el extremo izquierdo, que está marcado. La distancia del "cabezal" de una cinta a su extremo izquierdo, medida en número de casillas de cinta, representa el número natural en "el registro". Para DECrementar el número de casillas, el cabezal de la cinta se mueve hacia la izquierda; para INCREMENTAR, se mueve hacia la derecha. No es necesario imprimir ni borrar marcas en la cinta; las únicas instrucciones condicionales consisten en comprobar si el cabezal está en el extremo izquierdo, probando una marca de extremo izquierdo con una instrucción de "Saltar si está marcado".

Las siguientes instrucciones "mnemotécnicas", por ejemplo "CLR (r)", son arbitrarias; no existe ningún estándar.

La máquina de registros dispone, como memoria externa a su máquina de estados finitos , de una colección ilimitada (véase nota al pie | contable e ilimitada) de ubicaciones discretas y únicas , denominadas "registros". Estos registros almacenan únicamente números naturales ( cero y enteros positivos). Según una lista de instrucciones secuenciales en la tabla de la máquina de estados finitos, algunos tipos (por ejemplo, dos) de operaciones primitivas operan sobre el contenido de estos "registros". Finalmente, se dispone de una expresión condicional del tipo SI-ENTONCES-SINO para comprobar el contenido de uno o dos registros y "saltar" la máquina de estados finitos fuera de la secuencia de instrucciones predeterminada.

Modelo base 1 : El modelo más cercano a la visualización de Minsky (1961) y a la de Lambek (1961):

{ Incrementar el contenido del registro r, Disminuir el contenido del registro r, SI el contenido del registro r es cero ENTONCES Saltar a la instrucción 1z _SINOcontinuar con la siguiente instrucción }:

Modelo base 2 : El modelo "sucesor" (llamado así por la función sucesora de los axiomas de Peano ):

{ INCREMENTAR el contenido del registro r, BORRAR el contenido del registro r, SI el contenido del registro r _j ES IGUAL al contenido del registro r _kENTONCES saltar a la instrucción I _zSINO ir a la siguiente instrucción }

Modelo base 3 : Utilizado por Elgot-Robinson (1964) en su investigación de RASP acotados y no acotados : el modelo "sucesor" con COPY en lugar de CLEAR:

{ Incrementar el contenido del registro r, copiar el contenido del registro r _j al registro r _k , si el contenido del registro r _j es igual al contenido del registro r _k,entonces saltar a la instrucción 1 _z,de lo contrario ir a la siguiente instrucción }

Creación de "instrucciones de conveniencia" a partir de los conjuntos básicos.

Los tres conjuntos base 1, 2 o 3 mencionados anteriormente son equivalentes en el sentido de que se pueden crear las instrucciones de un conjunto utilizando las instrucciones de otro (un ejercicio interesante: una sugerencia de Minsky (1967) : declarar un registro reservado, por ejemplo, llámelo "0" (o Z de "cero" o E de "borrar") para que contenga el número 0). La elección del modelo dependerá de cuál le resulte más fácil de usar al autor en una demostración, una prueba, etc.

Además, a partir de los conjuntos base 1, 2 o 3 podemos crear cualquiera de las funciones recursivas primitivas (cf. Minsky (1967), Boolos-Burgess-Jeffrey (2002)). (Cómo ampliar el alcance para abarcar las funciones recursivas mu totales y parciales se discutirá en el contexto del direccionamiento indirecto). Sin embargo, construir las funciones recursivas primitivas es difícil porque los conjuntos de instrucciones son tan... primitivos (pequeños). Una solución es expandir un conjunto particular con "instrucciones de conveniencia" de otro conjunto:

Estas no serán subrutinas en el sentido convencional, sino bloques de instrucciones creados a partir del conjunto base y a los que se les asignará un mnemónico. Formalmente, para utilizar estos bloques necesitamos (i) "expandirlos" a sus equivalentes de instrucciones base ( lo que requerirá el uso de registros temporales o "auxiliares", por lo que el modelo debe tener esto en cuenta), o (ii) diseñar nuestras máquinas/modelos con las instrucciones "integradas".

Ejemplo: Conjunto base 1. Para crear CLR (r), utilice el bloque de instrucciones para contar hacia atrás el registro r hasta cero. Observe el uso de la sugerencia mencionada anteriormente:

CLR (r) = _equivalente
bucle : JZ (r, salir )

DEC (r)
JZ (0, bucle )

salida : etc.

Una vez más, todo esto es solo por conveniencia; nada de esto aumenta la potencia intrínseca del modelo.

Por ejemplo: el conjunto más expandido incluiría cada instrucción única de los tres conjuntos, más el salto incondicional J (z), es decir:

{ CLR (r), DEC (r), INC (r), CPY ( r _s , r _d ), JZ (r, z), JE ( r _j , r _k , z ), J(z) }

La mayoría de los autores eligen uno u otro de los saltos condicionales, por ejemplo Shepherdson-Sturgis (1963) usan el conjunto anterior menos JE (para ser perfectamente precisos usan JNZ – Jump if Not Zero en lugar de JZ; otra posible instrucción de conveniencia).

La operación "indirecta"

Ejemplo de direccionamiento indirecto

En nuestra vida cotidiana, la noción de "operación indirecta" no es inusual.

Ejemplo: Una búsqueda del tesoro.

En la ubicación "Tom_&_Becky's_cuve_in_pirate_chest" encontraremos un mapa que nos indicará dónde está "el tesoro":

(1) Vamos a la ubicación "La cueva de Tom y Becky..." y cavamos hasta encontrar una caja de madera.

(2) Dentro de la caja hay un mapa que indica la ubicación del tesoro: "debajo_del_porche_del_frente_de_Thatcher"

(3) Vamos al lugar "debajo del porche delantero de Thatcher", rompemos el hormigón con un martillo neumático y descubrimos "el tesoro": un saco de pomos de puerta oxidados.

La indirección especifica una ubicación identificada como el cofre pirata en "Tom_&_Becky's_cuve..." que actúa como un puntero a cualquier otra ubicación (incluida ella misma): su contenido (el mapa del tesoro) proporciona la "dirección" de la ubicación de destino "under_Thatcher's_front_porch" donde ocurre la acción real.

¿Por qué es necesaria una operación indirecta?: Dos problemas importantes del modelo de contador-máquina.

A continuación, hay que recordar que estos modelos son modelos abstractos con dos diferencias fundamentales respecto a cualquier cosa físicamente real: un número ilimitado de registros, cada uno con capacidades ilimitadas. El problema se manifiesta de forma más dramática cuando se intenta utilizar un modelo de máquina de contadores para construir una RASP que sea Turing equivalente y, por lo tanto, calcular cualquier función recursiva mu parcial :

Melzak (1961) añadió indirección a su modelo de "agujero y guijarro" para que este pudiera modificarse con un "goto calculado" y proporciona dos ejemplos de su uso ("Representación decimal en la escala de d" y "Ordenación por magnitud"; no está claro si estos se utilizan en su prueba de que el modelo es Turing equivalente, ya que "el programa en sí se deja al lector como ejercicio" (p. 292)). Minsky (1961, 1967) pudo demostrar que, con una codificación de números de Gödel adecuada (pero difícil de usar) , el modelo de registro no necesitaba indirección para ser Turing equivalente; pero sí necesitaba al menos un registro sin límites. Como se indica más adelante, Minsky (1967) insinúa el problema para un RASP, pero no ofrece una solución. Elgot y Robinson (1964) demostraron que su modelo RASP P ₀—que carece de capacidad de indirección— no puede calcular todas las "funciones secuenciales recursivas" (aquellas con parámetros de longitud arbitraria) si no tiene la capacidad de modificar sus propias instrucciones, pero sí puede hacerlo mediante números de Gödel si la tiene (págs. 395-397; en particular, figura 2 y nota al pie de la página 395). Por otro lado, su modelo RASP P' _0, equipado con un "registro de índice" (direccionamiento indirecto), puede calcular todas las "funciones secuenciales recursivas parciales" (las funciones recursivas mu) (págs. 397-398).

Cook y Reckhow (1973) lo expresan de la manera más concisa:

Las instrucciones indirectas son necesarias para que un programa fijo pueda acceder a un número ilimitado de registros a medida que varían las entradas." (p. 73)

Capacidades ilimitadas de los registros frente a capacidades limitadas de las instrucciones de la máquina de estados : La denominada parte de estados finitos de la máquina se supone que es , según la definición normal de algoritmo , muy finita tanto en el número de "estados" (instrucciones) como en el tamaño de las instrucciones (su capacidad para contener símbolos/signos). Entonces, ¿cómo mueve una máquina de estados una constante arbitrariamente grande directamente a un registro, por ejemplo, MOVE (k, r) (Mover la constante k al registro r)? Si se necesitan constantes enormes, deben comenzar en los propios registros o ser creadas por la máquina de estados utilizando un número finito de instrucciones, por ejemplo, subrutinas de multiplicación y suma usando INC y DEC (¡pero no un número casi infinito de estas!).

A veces, la constante k se crea mediante CLR(r) seguido de INC(r) repetido k veces ; por ejemplo, para colocar la constante k=3 en el registro r, es decir, 3 → r, de modo que al final de la instrucción [r]=3: CLR(r), INC(r), INC(r), INC(r). Este truco lo menciona Kleene (1952), pág. 223. El problema surge cuando el número que se va a crear agota el número de instrucciones disponibles para la máquina de estados finitos ; siempre hay una constante mayor que el número de instrucciones disponibles para la máquina de estados finitos .

Número ilimitado de registros frente a número limitado de instrucciones de máquina de estados : este problema es más grave que el primero. En particular, surge cuando intentamos construir una denominada RASP, una "máquina universal" (véase más información en Máquina de Turing universal ) que utiliza su máquina de estados finitos para interpretar un "programa de instrucciones" ubicado en sus registros ; es decir, estamos construyendo lo que hoy en día se denomina un ordenador con la arquitectura de von Neumann .

Observe que la máquina de estados finitos del contador debe llamar a un registro explícitamente (directamente) por su nombre/número: INC (65,356) llama explícitamente al registro número "65,365" . Si el número de registros excede la capacidad de la máquina de estados finitos para direccionarlos, entonces los registros fuera de los límites serán inaccesibles. Por ejemplo, si la máquina de estados finitos solo puede acceder a 65,536 = 2¹⁶ ^registros , ¿cómo puede acceder al registro 65,537?

¿Cómo accedemos a un registro que excede los límites de la máquina de estados finitos? Una opción sería modificar las instrucciones del programa (las almacenadas en los registros) para que contengan más de un comando. Sin embargo, esto también puede agotarse a menos que una instrucción tenga un tamaño (potencialmente) ilimitado. Entonces, ¿por qué no usar una única "superinstrucción" —un número realmente enorme— que contenga todas las instrucciones del programa codificadas? Así es como Minsky resuelve el problema, pero la numeración de Gödel que utiliza representa un gran inconveniente para el modelo, y el resultado no se parece en absoluto a nuestra noción intuitiva de una "computadora de programa almacenado".

Elgot y Robinson (1964) llegan a una conclusión similar con respecto a un RASP que es "determinado de forma finita". De hecho, puede acceder a un número ilimitado de registros (por ejemplo, para obtener instrucciones de ellos), pero solo si el RASP permite la "automodificación" de sus instrucciones de programa y ha codificado sus "datos" en un número de Gödel (Fig. 2, pág. 396).

En el contexto de un modelo más computacional que utiliza su instrucción RPT (repetir), Minsky (1967) nos tienta con una solución al problema (cf. p. 214, p. 259), pero no ofrece una resolución firme. Afirma:

«En general, una operación RPT no podría ser una instrucción en la parte de estado finito de la máquina... esto podría agotar cualquier cantidad particular de almacenamiento permitida en la parte finita de la computadora [sic, su nombre para sus modelos de RAM]. Las operaciones RPT requieren registros infinitos propios.» (p. 214).

Nos ofrece una RPT acotada que, junto con CLR(r) e INC(r), puede calcular cualquier función recursiva primitiva , y también la RPT no acotada citada anteriormente, que desempeña el papel del operador μ; esta, junto con CLR(r) e INC(r), puede calcular las funciones recursivas mu. Sin embargo, no aborda el concepto de "indirección" ni el modelo RAM propiamente dicho.

Según las referencias de Hartmanis (1971), parece que Cook (en sus apuntes de clase en la UC Berkeley, 1970) consolidó la noción de direccionamiento indirecto. Esto se aclara en el artículo de Cook y Reckhow (1973) , cuyo director de tesis de maestría fue Cook. El modelo de Hartmanis , muy similar al de Melzak (1961) , utiliza sumas y restas de dos y tres registros, así como copias de dos parámetros. El modelo de Cook y Reckhow reduce el número de parámetros (registros especificados en las instrucciones del programa) a una sola instrucción mediante el uso de un acumulador "AC".

La solución en pocas palabras: Diseñar nuestra máquina/modelo con indirección ilimitada : proporcionar un registro de "dirección" ilimitado que pueda nombrar (llamar) cualquier registro, independientemente de cuántos haya. Para que esto funcione, en general, el registro ilimitado requiere la capacidad de borrarse y luego incrementarse (y, posiblemente, decrementarse) mediante un bucle potencialmente infinito. En este sentido, la solución representa el operador μ ilimitado que puede, si es necesario, buscar indefinidamente a lo largo de la cadena ilimitada de registros hasta encontrar lo que busca. El registro de puntero es exactamente como cualquier otro registro con una excepción: en las circunstancias denominadas "direccionamiento indirecto", proporciona su contenido, en lugar del operando de dirección en la TABLA de la máquina de estados, como la dirección del registro de destino (¡incluido posiblemente él mismo!).

Indirección acotada y funciones recursivas primitivas

Si rechazamos el enfoque de Minsky de un número monstruoso en un registro, y especificamos que nuestro modelo de máquina será "como una computadora", tenemos que enfrentar este problema de indirección si queremos calcular las funciones recursivas (también llamadas funciones μ-recursivas ) , tanto las variedades totales como las parciales.

Nuestro modelo de máquina contadora más simple puede realizar una forma de indirección "limitada" —y , por lo tanto , calcular la subclase de funciones recursivas primitivas— mediante un "operador" recursivo primitivo llamado "definición por casos" (definido en Kleene (1952), pág. 229, y Boolos-Burgess-Jeffrey, pág. 74). Dicha "indirección limitada" es un proceso laborioso y tedioso. La "definición por casos" requiere que la máquina determine/distinguiera el contenido del registro de punteros intentando, una y otra vez hasta lograrlo, hacer coincidir dicho contenido con un número/nombre que el operador de casos declara explícitamente . Así, la definición por casos comienza, por ejemplo, desde la dirección del límite inferior y continúa indefinidamente hacia la dirección del límite superior intentando hacer una coincidencia.

¿El número en el registro N es igual a 0? Si no, ¿es igual a 1? ¿2? ¿3? ... ¿65364? Si no, entonces estamos en el último número, 65365, ¡y este más vale que sea el correcto, de lo contrario tendremos un problema!

La indirección "acotada" no nos permitirá calcular las funciones recursivas parciales ; para ello necesitamos la indirección no acotada, también conocida como el operador μ .

Supongamos que hubiéramos podido continuar hasta el número 65367, y que efectivamente ese registro tuviera lo que buscábamos. ¡Entonces habríamos podido completar nuestro cálculo con éxito! Pero supongamos que el 65367 no tuviera lo que necesitábamos. ¿Hasta dónde deberíamos seguir buscando?

Para ser equivalente a una máquina de Turing, el contador debe usar el desafortunado método de números de Minsky-Gödel de un solo registro , o bien, contar con la capacidad de explorar los extremos de su cadena de registros, hasta el infinito si es necesario. (El hecho de no encontrar algo "ahí fuera" define lo que significa que un algoritmo no termine; véase Kleene (1952), págs. 316 y siguientes, Capítulo XII, Funciones recursivas parciales , en particular págs. 323-325). Véase más información al respecto en el ejemplo siguiente.

Indirección no acotada y funciones recursivas parciales

Para lograr una indirección ilimitada , necesitamos un cambio de "hardware" en nuestro modelo de máquina. Una vez realizado este cambio, el modelo deja de ser una máquina de contadores para convertirse en una máquina de acceso aleatorio.

Ahora, cuando se especifica, por ejemplo, INC, la instrucción de la máquina de estados finitos deberá especificar de dónde provendrá la dirección del registro de interés. Esta dirección puede ser (i) la instrucción de la máquina de estados que proporciona una etiqueta explícita , o (ii) el registro puntero cuyo contenido es la dirección de interés. Siempre que una instrucción especifique una dirección de registro, también deberá especificar un parámetro adicional "i/d" – "indirecto/directo". En cierto modo, este nuevo parámetro "i/d" es un "interruptor" que permite obtener la dirección directa, tal como se especifica en la instrucción, o la dirección indirecta del registro puntero (cuyo registro puntero – en algunos modelos cualquier registro puede ser un registro puntero – se especifica en la instrucción). Esta "elección mutuamente excluyente pero exhaustiva" es otro ejemplo de "definición por casos", y el equivalente aritmético que se muestra en el ejemplo siguiente se deriva de la definición de Kleene (1952), pág. 229.

Ejemplo: CPY ( _origen indirecto , _origen r , _{destino directo,}_destino r )

Asigne un código para especificar el direccionamiento directo como d="0" y el direccionamiento indirecto como i="1". Entonces nuestra máquina puede determinar la dirección de origen de la siguiente manera:

i*[r _s ] + (1-i)*r _s

Por ejemplo, supongamos que el contenido del registro 3 es "5" (es decir, [3]=5) y el contenido del registro 4 es "2" (es decir, [4]=2):

Ejemplo: CPY ( 1, 3, 0, 4 ) = CPY ( indirecto, reg 3, directo, reg 4 )

1*[3] + 0*3 = [3] = dirección del registro fuente 5

0*[4] + 1*4 = 4 = dirección del registro de destino 4

Ejemplo: CPY ( 0, 3, 0, 4 )

0*[3] + 1*3 = 3 = dirección del registro fuente 3

0*[4] + 1*4 = 4 = dirección del registro de destino 4

Ejemplo: CPY ( 0, 3, 1, 4 )

0*[3] + 1*3 = 3 = dirección del registro fuente 3

1*[4] + 0*4 = [4] = dirección del registro de destino 2

La instrucción COPIA indirecta

Probablemente la más útil de las instrucciones añadidas sea COPY. De hecho, Elgot-Robinson (1964) dotan a sus modelos P ₀ y P' ₀ de las instrucciones COPY, y Cook-Reckhow (1973) dotan a su modelo basado en acumulador de solo dos instrucciones indirectas : COPY al acumulador indirectamente, COPY desde el acumulador indirectamente.

Una plétora de instrucciones : Debido a que cualquier instrucción que actúe sobre un solo registro puede ampliarse con su "dual" indirecto (incluidos saltos condicionales e incondicionales, cf. el modelo de Elgot-Robinson), la inclusión de instrucciones indirectas duplicará el número de instrucciones de un solo parámetro/registro (por ejemplo, INC (d, r), INC (i, r)). Peor aún, cada instrucción de dos parámetros/registros tendrá 4 posibles variantes, por ejemplo:

CPY (d, r _s , d, r _d ) = COPIA directamente del registro de origen directamente al registro de destino

CPY (i, r _sp , d, r _d ) = COPIA al registro de destino indirectamente utilizando la dirección de origen que se encuentra en el registro puntero de origen r _sp .

CPY (d, r _s , i, r _dp ) = COPIA el contenido del registro de origen indirectamente en el registro utilizando la dirección de destino que se encuentra en el registro puntero de destino r _dp .

CPY (i, r _sp , i, r _dp ) = COPIA indirectamente el contenido del registro de origen con dirección que se encuentra en el registro puntero de origen r _sp , en el registro de destino con dirección que se encuentra en el registro puntero de destino r _dp )

De manera similar, cada instrucción de tres registros que involucre dos registros fuente r _s1 r _s2 y un registro destino r _d dará como resultado 8 variedades, por ejemplo la suma:

[r _s1 ] + [r _s2 ] → r _d

producirá:

AGREGAR ( d, r _s1 , d, r _s2 , d, r _d )
AGREGAR ( i, r _sp1 , d, r _s2 , d, r _d )
AGREGAR ( d, r _s1 , i, r _sp2 , d, r _d )
AGREGAR ( i, r _sp1 , i, r _sp2 , d, r _d )
AGREGAR ( d, r _s1 , d, r _s2 , i, r _dp )
AGREGAR ( i, r _sp1 , d, r _s2 , i, r _dp )
AGREGAR ( d, r _s1 , i, r _sp2 , i, r _dp )
AGREGAR ( i, r _sp1 , i, r _sp2 , i, r _dp )

Si designamos un registro como "acumulador" (véase más abajo) e imponemos fuertes restricciones a las instrucciones permitidas, podemos reducir considerablemente la cantidad de operaciones directas e indirectas. Sin embargo, debemos asegurarnos de que el conjunto de instrucciones resultante sea suficiente, y debemos tener en cuenta que esta reducción implicará un mayor número de instrucciones por operación "significativa".

La noción de "acumulador A"

La convención histórica dedica un registro al acumulador, un "órgano aritmético" que literalmente acumula su número durante una secuencia de operaciones aritméticas:

«La primera parte de nuestro órgano aritmético... debería ser un órgano de almacenamiento paralelo que pueda recibir un número y sumarlo al que ya contiene, que también pueda borrar su contenido y almacenar lo que contiene. Llamaremos a dicho órgano Acumulador . Es un principio bastante convencional en las máquinas de cálculo pasadas y presentes de los tipos más variados, por ejemplo, multiplicadores de escritorio, contadores IBM estándar, máquinas de relés más modernas, la ENIAC » (negrita en el original: Goldstine y von Neumann, 1946; pág. 98 en Bell y Newell, 1971).

Sin embargo, el acumulador implica un mayor número de instrucciones por "operación" aritmética, en particular con respecto a las instrucciones denominadas "lectura-modificación-escritura", como "Incrementar indirectamente el contenido del registro al que apunta el registro r2". "A" designa el registro "acumulador" A:

Si nos atenemos a un nombre específico para el acumulador, por ejemplo "A", podemos implicar el acumulador en las instrucciones, por ejemplo,

INC ( A ) = INCA

Sin embargo, cuando escribimos las instrucciones CPY sin especificar el acumulador, las instrucciones son ambiguas o deben tener parámetros vacíos:

CPY ( d, r2, d, A ) = CPY (d, r2, , )

CPY ( d, A, d, r2 ) = CPY ( , , d, r2)

Históricamente, estas dos instrucciones CPY han recibido nombres distintos; sin embargo, no existe una convención. La tradición (por ejemplo, la computadora MIX imaginaria de Knuth (1973) ) utiliza dos nombres: LOAD y STORE. Aquí añadimos el parámetro "i/d":

LDA ( d/i, r _s ) = _def CPY ( d/i, r _s , d, A )

STA ( d/i, r _d ) = _def CPY ( d, A, d/i, r _d )

El modelo típico basado en acumulador utiliza para todas sus operaciones aritméticas y constantes de dos variables (por ejemplo, ADD (A, r), SUB (A, r)) (i) el contenido del acumulador, junto con (ii) el contenido de un registro específico. Las operaciones de una variable (por ejemplo, INC (A), DEC (A) y CLR (A)) solo requieren el acumulador. Ambos tipos de instrucciones almacenan el resultado (por ejemplo, suma, diferencia, producto, cociente o resto) en el acumulador.

Ejemplo: INCA = [A] + 1 → A

Ejemplo: ADDA (r _s ) = [A] + [r _s ] → A

Ejemplo: MULA (r _s ) = [A] * [r _s ] → A

Si así lo deseamos, podemos abreviar las reglas mnemotécnicas porque al menos un registro de origen y el registro de destino son siempre el acumulador A. Por lo tanto, tenemos :

{ LDA (i/d, r _s ), STA (i/d, r _d ), CLRA, INCA, DECA, ADDA (r _s ), SUBA (r _s ), MULA (r _s ), DIVA (r _s ), etc.)

La noción de registro de dirección indirecta "N"

Si nuestro modelo tiene un acumulador ilimitado, ¿podemos limitar el tamaño de todos los demás registros? No, a menos que contemos con al menos un registro ilimitado a partir del cual derivemos nuestras direcciones indirectas.

El enfoque minimalista consiste en utilizarlo a sí mismo (Schönhage lo hace).

Otro enfoque (Schönhage también lo utiliza) consiste en declarar un registro específico como el "registro de dirección indirecta" y limitar la indirección a este registro (el modelo RAM0 de Schönhage utiliza los registros A y N tanto para instrucciones indirectas como directas). De nuevo, nuestro nuevo registro no tiene un nombre convencional ; quizás "N" de "iNdex", o "iNdirect" o "número de dirección".

Para lograr la máxima flexibilidad, como hemos hecho con el acumulador A , consideraremos N simplemente como otro registro sujeto a incremento, decremento, borrado, prueba, copia directa, etc. De nuevo, podemos reducir la instrucción a un único parámetro que permita la dirección y la indirección, por ejemplo.

LDAN (i/d) = CPY (i/d, N, d, A); Acumulador de carga a través del registro de dirección iN

STAN (i/d) = CPY (d, A, i/d, N). Acumulador de almacenamiento a través del registro iNdirection.

¿Por qué este enfoque es tan interesante? Al menos por dos razones:

(1) Un conjunto de instrucciones sin parámetros:

Schönhage hace esto para producir su conjunto de instrucciones RAM0. Véase la sección siguiente.

(2) Reducir una RAM a una máquina post-Turing:

Haciéndonos pasar por minimalistas, reducimos todos los registros, excepto el acumulador A y el registro de indirección N, por ejemplo, r = { r0, r1, r2, ... }, a una cadena ilimitada de compartimentos de capacidad (muy) limitada. Estos no harán más que almacenar números (muy) limitados, por ejemplo, un solo bit con valor { 0, 1 }. De igual manera, reducimos el acumulador a un solo bit. Restringimos cualquier operación aritmética a los registros { A, N }, usamos operaciones indirectas para extraer el contenido de los registros al acumulador y escribimos 0 o 1 desde el acumulador a un registro:

{ LDA (i, N), STA (i, N), CLR (A/N), INC (A/N), DEC(N), JZ (A/N, I _z ), JZ (I _z ), H }

Vamos más allá y eliminamos A por completo mediante el uso de dos registros "constantes" llamados "ERASE" e "PRINT": [ERASE]=0, [PRINT]=1.

{ CPY (d, BORRAR, i, N), CPY (d, IMPRIMIR, i, N), CLR (N), INC (N), DEC (N), JZ (i, N, I _z ), JZ (I _z ), H }

Renombra las instrucciones COPY y llama INC (N) = DERECHA, DEC (N) = IZQUIERDA y tendremos las mismas instrucciones que la máquina Post-Turing, más un CLRN adicional :

{ BORRAR, IMPRIMIR, LIMPIAR, DERECHA, IZQUIERDA, JZ (i, N, I _z ), JZ (I _z ), H }

Equivalencia de Turing de la RAM con indirección

En la sección anterior mostramos informalmente que una RAM con capacidad de indirección ilimitada produce una máquina post-Turing . La máquina post-Turing es equivalente a Turing, por lo que hemos demostrado que la RAM con indirección es equivalente a Turing.

Aquí presentamos una demostración un poco más formal. Comencemos diseñando nuestro modelo con tres registros reservados "E", "P" y "N", además de un conjunto ilimitado de registros 1, 2, ..., n a la derecha. Los registros 1, 2, ..., n se considerarán "los cuadrados de la cinta". El registro "N" apunta al "cuadrado escaneado" que "el cabezal" está observando actualmente. El "cabezal" puede considerarse en el salto condicional ; observe que utiliza direccionamiento indirecto (cf. Elgot-Robinson, pág. 398). A medida que decrementamos o incrementamos "N", el cabezal (aparente) se "moverá a la izquierda" o "a la derecha" a lo largo de los cuadrados. Moveremos el contenido de "E"=0 o "P"=1 al "cuadrado escaneado" al que apunta N, utilizando el CPY indirecto.

El hecho de que nuestra cinta esté terminada a la izquierda nos presenta un pequeño problema: cada vez que se produce LEFT, nuestras instrucciones tendrán que comprobar si el contenido de "N" es cero o no; si es así, debemos dejar su contador en "0" (esta es nuestra elección como diseñadores ; por ejemplo, podríamos hacer que la máquina/modelo "active un evento" de nuestra elección).

Conjunto de instrucciones 1 (aumentado): { INC (N), DEC (N), CLR (N), CPY (d, r _s ,i, N), JZ ( i, r, z ), HALT }

La siguiente tabla define las instrucciones Post-Turing en términos de sus instrucciones equivalentes en RAM y proporciona un ejemplo de su funcionamiento. La ubicación (aparente) del cabezal a lo largo de la cinta de registros r0-r5 . . . se muestra sombreada:

Ejemplo: La indirección limitada produce una máquina que no es equivalente a Turing.

A lo largo de esta demostración debemos tener en cuenta que las instrucciones en la TABLA de la máquina de estados finitos son limitadas , es decir, finitas :

"Además de ser simplemente un conjunto finito de reglas que proporciona una secuencia de operaciones para resolver un tipo específico de problema, un algoritmo tiene cinco características importantes [finitud, definición, entrada, salida, efectividad]" (cursiva añadida, Knuth págs. 4-7).

La dificultad surge porque los registros tienen "nombres" (números) explícitos y nuestra máquina debe llamarlos por su nombre para poder "acceder" a ellos.

Construiremos el CPY indirecto (i, q, d, φ) con el operador CASE. La dirección del registro de destino se especificará mediante el contenido del registro "q"; una vez que el operador CASE haya determinado este número, el CPY depositará directamente el contenido del registro con dicho número en el registro "φ". Necesitaremos un registro adicional que llamaremos "y" ; este registro funcionará como contador ascendente.

Por lo tanto, lo siguiente es en realidad una demostración constructiva o prueba de que podemos simular el CPY indirecto (i, q, d, φ) sin un cambio de diseño de "hardware" en nuestra máquina/modelo de contador. Sin embargo, tenga en cuenta que debido a que este CPY indirecto está "limitado" por el tamaño/extensión de la máquina de estados finitos, un RASP que utilice este CPY indirecto solo puede calcular las funciones recursivas primitivas , no el conjunto completo de funciones recursivas mu .

El operador CASE se describe en Kleene (1952) (p. 229) y en Boolos-Burgess-Jeffrey (2002) (p. 74); estos últimos autores destacan su utilidad. La siguiente definición se basa en la de Kleene, pero se ha modificado para reflejar la conocida estructura "IF-THEN-ELSE".

El operador CASE "devuelve" un número natural a φ dependiendo de qué "caso" se cumpla, comenzando con "case_0" y pasando sucesivamente por "case_last"; si no se cumple ningún caso, se devuelve a φ el número llamado "default" (también conocido como "woops") (aquí x designa alguna selección de parámetros, por ejemplo, el registro q y la cadena r0, ... rlast):

Definición por casos φ ( x , y):

caso_0: SI Q ₀ ( x , y) es verdadero ENTONCES φ ₀ ( x , y) SINO
caso_1: SI Q ₁ ( x , y) es verdadero ENTONCES φ ₁ ( x , y) SINO
casos_2 hasta el caso_penúltimo: etc. . . . . . . . . DE LO CONTRARIO
case_last: SI Q _last ( x , y) es verdadero ENTONCES φ _last ( x , y) SINO
predeterminado: hacer φ _{predeterminado} ( x , y)

Kleene exige que los "predicados" Q _n que realizan las pruebas sean todos mutuamente excluyentes ; los "predicados" son funciones que producen solo { verdadero, falso } como resultado; Boolos-Burgess-Jeffrey añade el requisito de que los casos sean "exhaustivos".

Comenzamos con un número en el registro q que representa la dirección del registro de destino. Pero, ¿cuál es este número? Los "predicados" lo probarán para averiguarlo, una prueba tras otra: JE (q, y, z) seguido de INC (y). Una vez que el número se identifica explícitamente, el operador CASE copia directamente/explícitamente el contenido de este registro a φ:

Definición por casos CPY (i, q, d, φ) = _def φ (q, r0, ..., rlast, y) =

caso_0: SI CLR (y), [q] - [y]=0 ENTONCES CPY ( r0, φ ), J (salir) SINO
caso_1: SI INC (y), [q] = [y]=1 ENTONCES CPY ( r1, φ ), J (salir) SINO
caso_2 a caso n: SI . . . ENTONCES . . . SINO
caso_n: SI INC (y), [q] = [y]=n ENTONCES CPY ( rn, φ ), J (salir) SINO
caso_n+1 a caso_último: SI . . . ENTONCES . . . SINO
case_last: SI INC (y), [q] = [y]="last" ENTONCES CPY ( rlast, φ ), J (exit) SINO
predeterminado: ups

El caso_0 (el paso base de la recursión en y) se ve así:

caso_0 :

CLR ( y ) ; establece el registro y = 0
JE ( q, y, _φ0 )
J ( caso_1 )

_φ0: CPY ( r0, φ )
J ( salida )

caso_1: etc.

El caso n (el paso de inducción) se ve así; recuerde que cada instancia de "n", "n+1", ..., "last" debe ser un número natural explícito:

caso_n :

INC (y)
JE ( q, y, _φn )
J ( caso_n+1 )

_φn: CPY ( rn, φ )
J ( salida )

caso__n+1: etc.

Case_last detiene la inducción y limita el operador CASE (y, por lo tanto, limita el operador de "copia indirecta"):

caso_último :

INC (y)
JE ( q, y, _φúltimo )
J ( ups )

_φlast : CPY ( rlast, φ )
J ( salida )

¡Ups!: ¿Cómo gestionamos un intento de salir de los límites del campo?
salida: etc.

Si el CASE pudiera continuar hasta el infinito, sería el operador mu . Pero no puede : el "registro de estado" de su máquina de estados finitos ha alcanzado su conteo máximo (por ejemplo, 65365 = 11111111,11111111 ₂ ) o su tabla se ha quedado sin instrucciones; después de todo, es una máquina finita .

Ejemplos de modelos

Modelo de registro a registro ("lectura-modificación-escritura") de Cook y Reckhow (1973)

El modelo de Cook y Rechkow, que se encuentra con frecuencia, es un poco como el modelo de Malzek de registro ternario (escrito con la mnemotecnia de Knuth ; las instrucciones originales no tenían ninguna mnemotecnia excepto TRA, Read, Print).

LOAD ( C, r_d ) ; C → r_d, C es cualquier número entero

Ejemplo: LOAD ( 0, 5 )borrará el registro 5.

ADD ( r_s1, r_s2, r_d ) ; [r_s1] + [r_s2] → r_dLos registros pueden ser iguales o diferentes;

Ejemplo: ADD ( A, A, A )duplicará el contenido del registro A.

SUB ( r_s1, r_s2, r_d ) ; [r_s1] - [r_s2] → r_dLos registros pueden ser iguales o diferentes:

Ejemplo: SUB ( 3, 3, 3 )borrará el registro 3.

COPY ( i, r_p, d, r_d ) ; [[r_p] ] → r_d, Copia indirectamente el contenido del registro de origen al que apunta el registro de puntero r _p en el registro de destino.
COPY ( d, r_s, i, r_p ) ; [r_s] → [r_p]. Copia el contenido del registro de origen rs _en el registro de destino al que apunta el registro de puntero _rp .
JNZ ( r, I_z ) ;Salto condicional si [r] es positivo; es decir, SI [r] > 0 ENTONCES saltar a la instrucción z, de lo contrario continuar en secuencia (Cook y Reckhow lo llaman: "Transferir el control a la línea m si Xj > 0").
READ ( r_d ) ;Copiar "la entrada" en el registro de destino r _d
PRINT ( r_s ) ;Copiar el contenido del registro fuente r _s a "la salida".

RAM0 y RAM1 de Schönhage (1980)

Schönhage (1980) describe un modelo atomizado muy primitivo elegido para su demostración de la equivalencia de su modelo de máquina de punteros SMM :

"Para evitar cualquier direccionamiento explícito, la RAM0 tiene el acumulador con contenido z y un registro de direcciones adicional con contenido actual n (inicialmente 0)" (p. 494)

Modelo RAM1 : Schönhage demuestra cómo su construcción puede utilizarse para formar la forma más común y utilizable de RAM tipo "sucesor" (utilizando las mnemotecnias de este artículo):

LDA k ; k --> A , k es una constante, un número explícito como "47"
LDA ( d, r ) ; [r] → A ;Cargar directamente A
LDA ( i, r ) ; [[r]] → A ;carga indirecta A
STA ( d, r ) ; [A] → r ;almacenar directamente A
STA ( i, r ) ; [A] → [r] ;almacenar indirectamente A
JEA ( r, z ) ; IF [A] = [r] then I_z else continue
INCA ; [A] + 1 --> A

Modelo RAM0 : La máquina RAM0 de Schönhage tiene 6 instrucciones indicadas por una sola letra (la sexta "C xxx" parece implicar "saltar el siguiente parámetro"). Schönhage designó el acumulador con "z", "N" con "n", etc. En lugar de las reglas mnemotécnicas de Schönhage, utilizaremos las reglas mnemotécnicas desarrolladas anteriormente.

(Z), CLRA: 0 → A
(A), INCA: [A] +1 → A
(N), CPYAN: [A] → N
(A), LDAA: [[A]] → A ; el contenido de A apunta a la dirección del registro; coloque el contenido del registro en A.
(S), STAN: [A] → [N] ; el contenido de N apunta a la dirección del registro; coloque el contenido de A en el registro al que apunta N.
(C), JAZ ( z ): [A] = 0 then go to I_z; ambiguo en su tratamiento

La indirección proviene (i) de CPYAN (copiar/transferir contenido A a N) que trabaja con store_A_via_N STAN, y de (ii) la peculiar instrucción de indirección .LDAA ( [[A]] → [A] )

Notas a pie de página

Finito versus ilimitado

El hecho de que cualquier tipo de máquina contadora sin un registro de direcciones ilimitado deba especificar un registro "r" por su nombre indica que el modelo requiere que "r" sea finito , aunque sea "ilimitado" en el sentido de que el modelo no implica un límite superior al número de registros necesarios para realizar su(s) función(es). Por ejemplo, no requerimos que r < 83.617.563.821.029.283.746 ni r < 2^1.000.001, etc.

Por lo tanto, nuestro modelo puede "expandir" el número de registros, si es necesario para realizar un cálculo determinado. Sin embargo, esto implica que cualquier número al que se expanda el modelo debe ser finito ; debe poder indexarse con un número natural: ω no es una opción .

Podemos sortear esta restricción proporcionando un registro sin límites para indicar la dirección del registro que especifica una dirección indirecta.

Véase también

Enlaces externos

Emulador de máquina de acceso aleatorio
Emulador de máquina de acceso aleatorio
Emulador de máquina de acceso aleatorio

Referencias

^ Érdi, Gergő (6 de septiembre de 2010). "De Register Machines a Brainfuck, parte 1" . Consultado el 7 de febrero de 2024 .

Salvo algunas excepciones, estas referencias son las mismas que las de la máquina de registro .

- Goldstine, Herman H., y von Neumann, John, «Planificación y codificación de los problemas para un instrumento de computación electrónica», Informe de 1947, Instituto de Estudios Avanzados , Princeton. Reimpreso en las págs. 92-119 en Bell, C. Gordon y Newell, Allen (1971), Estructuras informáticas: lecturas y ejemplos , McGraw-Hill Book Company, Nueva York. ISBN 0-07-004357-4}.
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: es 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 que se tratan y comparan en profundidad : la máquina de Turing (aún en la forma original de 4-tuplas de Boolos) y la recursión son los otros dos.
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 (1973), Máquinas de acceso aleatorio con límite de tiempo , Journal of Computer Systems Science 7(4):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. Vyssots 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). The Annals of Mathematics, Vol. 74, No. 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.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 , «Modelos y simulaciones de máquinas», págs. 3-66, en: Jan van Leeuwen , ed. Manual de informática teórica. Volumen A: Algoritmos y complejidad , 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.

[1] Érdi, Gergő (6 de septiembre de 2010). "De Register Machines a Brainfuck, parte 1" . Consultado el 7 de febrero de 2024 .

[ 1 ]