Máquina de acceso aleatorio

Este artículo trata sobre la máquina abstracta. Para otros usos, consulte Ram .

Este artículo tiene varios problemas. Ayude a mejorarlo o discuta estos problemas en la página de discusión . ( Obtenga información sobre cómo y cuándo eliminar estos mensajes de plantilla ) Este artículo incluye una lista de referencias generales , pero permanece en gran parte sin verificar porque carece de suficientes citas en línea correspondientes . Ayude a mejorar este artículo introduciendo citas más precisas. ( Diciembre de 2017 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla ) Este artículo puede ser demasiado técnico para que la mayoría de los lectores lo comprendan . Ayude a mejorarlo para que sea comprensible para los no expertos , sin eliminar los detalles técnicos. ( Diciembre de 2017 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla ) Es posible que el tono o estilo de este artículo no refleje el tono enciclopédico utilizado en Wikipedia . Consulte la guía de Wikipedia para escribir mejores artículos para obtener sugerencias. ( Diciembre de 2017 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla ) ( Aprenda cómo y cuándo eliminar este mensaje de plantilla )

En informática , la máquina de acceso aleatorio ( RAM ) es una máquina abstracta en la clase general de máquinas de registro . La RAM es muy similar a la máquina contadora pero con la capacidad adicional de "direccionamiento indirecto" de sus registros. Al igual que la máquina de contador, la RAM tiene sus instrucciones en la parte de estado finito de la máquina (la llamada arquitectura de Harvard ).

El equivalente de RAM de la máquina universal de Turing  , con su programa en los registros y sus datos, se denomina máquina de programa almacenado de acceso aleatorio o RASP. Es un ejemplo de la llamada arquitectura de von Neumann y está más cerca de la noción común de computadora .

Junto con las máquina de Turing y modelos counter-máquina , los modelos RAM y RASP se utilizan para el análisis de la complejidad computacional . Van Emde Boas (1990) llama a estos tres modelos más la máquina puntero " máquina secuencial", para distinguirlos de los modelos de "máquina paralela de acceso aleatorio ".

Introducción al modelo

El concepto de máquina de acceso aleatorio (RAM) comienza con el modelo más simple de todos, el llamado modelo de máquina contador . Sin embargo, dos adiciones lo alejan de la máquina de mostrador. El primero mejora la máquina con la conveniencia del direccionamiento indirecto; el segundo mueve el modelo hacia la computadora más convencional basada en acumuladores con la adición de uno o más registros auxiliares (dedicados), el más común de los cuales se llama "el acumulador".

Definición formal

Una máquina de acceso aleatorio (RAM) es un modelo de máquina computacional abstracto idéntico a una máquina contadora de registros múltiples con la adición de direccionamiento indirecto. A discreción de una instrucción de la TABLA de su máquina de estados finitos , la máquina deriva una dirección de registro "objetivo" ya sea (i) directamente de la instrucción en sí, o (ii) indirectamente del contenido (por ejemplo, número, etiqueta) de la 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 número natural único. Para mayor precisión usaremos el simbolismo cuasi formal de Boolos-Burgess-Jeffrey (2002) para especificar un registro, su contenido y una operación en un registro:

• [r] significa "el contenido del registro con dirección r". La etiqueta "r" aquí es una "variable" que puede llenarse con un número natural o 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 la dirección" 3 ", más 1, se coloca en el registro de destino con la dirección" 3 "(aquí el origen y el destino son el mismo lugar). Si [3] = 37, es decir, el contenido de el registro 3 es el número "37", luego 37 + 1 = 38 se colocará en el registro 3.

Ejemplo: [3] → 5; significa "El contenido del registro de origen con la dirección" 3 "se coloca en el registro de destino con la 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 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 es aquella que especifica en la propia instrucción la dirección del registro de origen o destino cuyo contenido será objeto de la instrucción. Definición: Una instrucción indirecta es aquella que especifica un "registro de puntero", cuyo contenido es la dirección de un registro "objetivo". El registro de destino puede ser un origen o un destino (las diversas instrucciones COPY proporcionan ejemplos de esto). Un registro puede dirigirse a sí mismo indirectamente.

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

Ejemplo: COPY ( d , A, i , n) medios directamente d obtener la dirección del registro de origen (registro "A") de la instrucción en sí, sino indirectamente i obtener la dirección de destino desde un puntero a registrar N. Supongamos [N] = 3, entonces el registro 3 es el destino y la instrucción hará lo siguiente: [A] → 3.

Definición: la instrucción utiliza el contenido del registro fuente . La dirección del registro de origen se puede especificar (i) directamente mediante la instrucción o (ii) indirectamente mediante el registro de puntero especificado por la instrucción.

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

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

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

Actualización: El modelo de contra-máquina

Melzak (1961) proporciona una visualización fácil de una máquina contador: sus "registros" son agujeros en el suelo, y estos agujeros contienen guijarros. Según una instrucción, dentro y fuera de estos agujeros "la computadora" (persona o máquina) agrega (INCREMENTOS) o quita (DECREMENTOS) un solo guijarro. Según sea necesario, los guijarros adicionales provienen y el exceso de guijarros regresa a un suministro infinito; si el agujero es demasiado pequeño para acomodar los guijarros, la "computadora" cava el agujero más grande.

Minsky (1961) y Hopcroft-Ullman 1979 (p. 171) ofrecen la visualización de una máquina de Turing de varias cintas con tantas cintas de extremo izquierdo como "registros". La longitud de cada cinta es ilimitada a la derecha y cada cuadrado está en blanco, excepto el extremo izquierdo, que está marcado. La distancia de la "cabeza" de una cinta desde su extremo izquierdo, medida en números de cuadrados de cinta, representa el número natural en "el registro". Para disminuir el recuento de cuadrados, el cabezal de la cinta se mueve hacia la izquierda; Incremento se mueve a la derecha. No es necesario imprimir o borrar marcas en la cinta; las únicas instrucciones condicionales son verificar si la cabeza está en el extremo izquierdo, probando una marca en el extremo izquierdo con una "instrucción Saltar si está marcada".

Las siguientes instrucciones "mnemónicos", por ejemplo, "CLR (r)" son arbitrarias; no existe ningún estándar.

La máquina de registro tiene, para una memoria externa a su máquina de estado finito, una colección ilimitada (cf: nota al pie | contable e ilimitada) de ubicaciones discretas y etiquetadas de forma única con capacidad ilimitada , llamadas "registros". Estos registros contienen solo números naturales (cero y los enteros positivos). Según una lista de instrucciones secuenciales en la TABLA de la máquina de estados finitos, algunos (por ejemplo, 2) tipos de operaciones primitivas operan sobre el contenido de estos "registros". Finalmente, una expresión condicional en forma de IF-THEN-ELSE está disponible para probar el contenido de uno o dos registros y "bifurcar / 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 Lambek (1961):

• {Incremento del contenido del registro r, Decremento del contenido del registro r, SI el contenido del registro r es cero ENTONCES Salta a la instrucción I _z ELSE continúa a la siguiente instrucción}:

Instrucción	Mnemotécnico	Acción sobre el registro (s) "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

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, IF contenido del registro r _j es igual a la contenido del registro r _k ENTONCES Saltar a la instrucción I _z ELSE GOTO para siguiente instrucción}

Instrucción	Mnemotécnico	Acción sobre el registro (s) "r"	Acción en el registro de instrucciones de la máquina de estados finitos, IR
Claro	CLR (r)	0 → r	[IR] + 1 → IR
Incremento	INC (r)	[r] + 1 → r	[IR] + 1 → IR
Saltar si es igual	JE (r1, r2, z)	ninguno	SI [r1] = [r2] ENTONCES z → IR ELSE [IR] + 1 → IR
Detener	H	ninguno	[IR] → IR

Modelo base 3 : utilizado por Elgot-Robinson (1964) en su investigación de los RASP limitados y no limitados: 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 Igual al contenido del registro r _k luego saltar a la instrucción I _z ELSE ir a la siguiente instrucción}

Instrucción	Mnemotécnico	Acción sobre el registro (s) "r"	Acción en el registro de instrucciones de la máquina de estados finitos, IR
COPIAR	COPIA (r1, r2)	[r1] → r2	[IR] + 1 → IR
Incremento	INC (r)	[r] + 1 → r	[IR] + 1 → IR
Saltar si es igual	JE (r1, r2, z)	ninguno	SI [r1] = [r2] ENTONCES z → IR ELSE [IR] + 1 → IR
Detener	H	ninguno	[IR] → IR

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

Los tres conjuntos básicos 1, 2 o 3 anteriores son equivalentes en el sentido de que se pueden crear las instrucciones de un conjunto utilizando las instrucciones de otro conjunto (un ejercicio interesante: una pista de Minsky (1967) - declarar un registro reservado, por ejemplo, llamar es "0" (o Z para "cero" o E para "borrar") para contener el número 0). La elección del modelo dependerá de cuál sea el autor que encuentre más fácil de usar 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 la red para capturar 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 (diminutos). Una solución es expandir un conjunto en 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 dará un mnemónico. En un sentido formal, para usar estos bloques necesitamos (i) "expandirlos" a sus equivalentes de instrucción base; requerirán 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) use el bloque de instrucciones para contar el registro r hasta cero. Observe el uso de la sugerencia mencionada anteriormente:

• CLR (r) = _equiv
• bucle : JZ (r, salir )

• DEC (r)
• JZ (0, bucle )

• salida : etc.

Nuevamente, todo esto es solo por conveniencia; nada de esto aumenta el poder intrínseco 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) usa 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 diaria, la noción de una "operación indirecta" no es inusual.

Ejemplo: una búsqueda del tesoro.

En la ubicación "Tom _ & _ Becky's_cave_in_pirate_chest" será donde podremos encontrar un mapa que nos dirija al "tesoro":

(1) Vamos a la ubicación "Tom _ & _ Becky's_cave ..." y excavamos hasta encontrar una caja de madera.

(2) Dentro de la caja hay un mapa de la ubicación del tesoro: "under_Thatcher's_front_porch"

(3) Vamos a la ubicación "under_Thatcher's_front_porch", martillamos el concreto y descubrimos "el tesoro": un saco de picaportes oxidados.

Indirection especifica una ubicación identificada como el cofre pirata en "Tom _ & _ Becky's_cave ..." que actúa como un puntero a cualquier otra ubicación (incluido él mismo): su contenido (el mapa del tesoro) proporciona la "dirección" de la ubicación objetivo "debajo de_Thatcher 's_front_porch "donde está ocurriendo la acción real.

Por qué la necesidad de una operación indirecta: dos problemas importantes con el modelo de contra-máquina

A continuación, uno debe recordar que estos modelos son modelos abstractos con dos diferencias fundamentales con respecto a cualquier cosa físicamente real: números ilimitados de registros, cada uno con capacidades ilimitadas. El problema aparece más dramáticamente cuando se intenta usar un modelo de máquina contraria para construir un RASP que sea equivalente a Turing y así calcular cualquier función recursiva mu parcial :

• Melzak (1961) agregó indirección a su modelo de "agujero y guijarro" para que su modelo 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 el equivalente de Turing, ya que" el programa en sí se deja al lector como un ejercicio "(p. 292)). Minsky (1961, 1967) pudo demostrar que, con una codificación numérica de Gödel adecuada (pero difícil de usar) , el modelo de registro no necesitaba direccionamiento indirecto para ser equivalente a Turing; pero necesitaba al menos un registro ilimitado. Como se indica a continuación, Minsky (1967) insinúa el problema de un RASP pero no ofrece una solución.Elgot y Robinson (1964) demostraron que su modelo RASP P ₀ - no tiene capacidad de direccionamiento indirecto - no puede calcular todas las "funciones secuenciales recursivas" (aquellas que tienen parámetros de longitud arbitraria) si no tiene la capacidad de modificar sus propias instrucciones, pero puede hacerlo mediante números de Gödel si la tiene (p. 395 -397; en particular figura 2 y nota a pie de página p. 395). Por otro lado, su modelo RASP P ' ₀ equipado con un "registro de índice" (direccionamiento indirecto) puede calcular todas las "funciones secuenciales recursivas parciales" (las funciones recursivas mu) (p. 397-398).

Cook y Reckhow (1973) lo dicen de la manera más sucinta:

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

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

A veces, la constante k se creará mediante el uso de CLR (r) seguido de INC (r) repetido k veces, por ejemplo, para poner la constante k = 3 en el registro r, es decir, 3 → r, por lo que al final de la instrucción [r ] = 3: CLR (r), INC (r), INC (r), INC (r). Este truco es mencionado por Kleene (1952) p. 223. El problema surge cuando el número 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 .

• No acotadas número de registros en comparación con las instrucciones de máquina de estados delimitadas : Esto es más grave que el primer problema. En particular, este problema surge cuando intentamos construir un llamado RASP, una "máquina universal" (ver más en Universal Turing machine ) que usa 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 llama una computadora con la arquitectura de von Neumann .

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

Entonces, ¿cómo hacemos nos dirigimos a un registro más allá de los límites de la máquina de estados finitos? Un enfoque sería modificar las instrucciones del programa (las almacenadas en los registros) para que contengan más de un comando. Pero esto también puede agotarse a menos que una instrucción tenga un tamaño (potencialmente) ilimitado. Entonces, ¿por qué no usar solo una "superinstrucción", un número realmente grande, que contiene todas las instrucciones del programa codificadas en él? 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 nada a nuestra noción intuitiva de una "computadora con programa almacenado".

Elgot y Robinson (1964) llegan a una conclusión similar con respecto a un RASP que está "determinado de manera 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 "auto modificación" de las instrucciones de su programa y ha codificado sus "datos" en un número de Gödel (Fig. 2 p. 396 ).

En el contexto de un modelo más parecido a una computadora que usa su instrucción RPT (repetición), Minsky (1967) nos atormenta 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 permitido en la parte finita de la computadora [sic, su nombre para sus modelos de RAM]. Las operaciones de RPT requieren infinitos registros propios ". (pág.214).

Nos ofrece un RPT acotado que, junto con CLR (r) e INC (r), puede calcular cualquier función recursiva primitiva , y ofrece el RPT ilimitado citado anteriormente que desempeña el papel de operador μ; junto con CLR (r) e INC (r) pueden calcular las funciones recursivas mu. Pero no discute la "indirecta" o el modelo RAM per se.

A partir de las referencias en Hartmanis (1971), parece que Cook (en sus notas de conferencia mientras estaba en UC Berkeley, 1970) ha reafirmado la noción de direccionamiento indirecto. Esto se vuelve más claro en el artículo de Cook y Reckhow (1973): Cook es el asesor de tesis de maestría de Reckhow. El modelo de Hartmanis, bastante similar al modelo de Melzak (1961), utiliza sumas y restas de dos y tres registros y copias de dos parámetros; El modelo de Cook y Reckhow reduce el número de parámetros (registros llamados en las instrucciones del programa) a una llamada mediante el uso de un acumulador "AC".

La solución en pocas palabras: Diseñe nuestra máquina / modelo con direccionamiento indirecto ilimitado  : proporcione un registro de "direcciones" ilimitado que potencialmente pueda nombrar (llamar) cualquier registro sin importar cuántos haya. Para que esto funcione, en general, el registro ilimitado requiere la capacidad de ser borrado y luego incrementado (y, posiblemente, decrementado) por un bucle potencialmente infinito. En este sentido, la solución representa el operador μ ilimitado que puede, si es necesario, cazar ad infinitim 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 estado, para que sea la dirección del registro de destino (¡incluido posiblemente él mismo!).

Indirección limitada y funciones recursivas primitivas

Si evitamos 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 μ-recursive funciones ) - tanto variedades totales como parciales.

Nuestro modelo de contra-máquina más simple puede realizar una forma "acotada" de indirección - y así calcular la subclase de funciones recursivas primitivas  - usando un "operador" recursivo primitivo llamado "definición por casos" (definido en Kleene (1952) p 229 y Boolos-Burgess-Jeffrey p. 74). Esta "indirecta limitada" es un asunto laborioso y tedioso. La "definición por casos" requiere que la máquina determine / distinga el contenido del registro de puntero intentando, una y otra vez hasta el éxito, hacer coincidir este contenido con un número / nombre que el operador de caso declare explícitamente . Por lo tanto, la definición por casos comienza, por ejemplo, en la dirección del límite inferior y continúa hasta la saciedad hacia la dirección del límite superior intentando hacer una coincidencia:

¿Es el número en el registro N igual a 0? Si no es así, ¿es igual a 1? 2? 3? ... 65364? Si no, entonces estamos en el último número 65365 y será mejor que este sea el indicado, ¡de lo contrario tenemos un problema!

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

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

Para ser equivalente a Turing, la máquina contadora debe utilizar el desafortunado método numérico de Minsky Gödel de registro único , o ser aumentada con la capacidad de explorar los extremos de su cadena de registro, ad infinitum 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 sig. Capítulo XII Funciones recursivas parciales , en particular págs. 323-325.) Ver más sobre esto en el siguiente ejemplo.

Indirección ilimitada y funciones recursivas parciales

Para la indirección ilimitada , necesitamos un cambio de "hardware" en nuestro modelo de máquina. Una vez que hacemos este cambio, el modelo ya no es una máquina de contador, sino una máquina de acceso aleatorio.

Ahora, cuando se especifica, por ejemplo, INC, la instrucción de la máquina de estados finitos tendrá que especificar de dónde vendrá la dirección del registro de interés. Este dónde puede ser (i) la instrucción de la máquina de estado que proporciona una etiqueta explícita , o (ii) el registro de puntero cuyo contenido es la dirección de interés. Siempre que una instrucción especifique una dirección de registro, ahora tambiénes necesario especificar un parámetro adicional "i / d" - "indirecto / directo". En cierto sentido, este nuevo parámetro "i / d" es un "interruptor" que cambia de una forma para obtener la dirección directa como se especifica en la instrucción o de la otra forma para obtener la dirección indirecta del registro de puntero (qué registro de puntero - en algunos modela cada registro puede ser un registro de puntero (lo especifica 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. 229.

Ejemplo: CPY ( _fuente indirecta , _fuente 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:

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

Por ejemplo, suponga 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 de registro de origen 5

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

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

0 * [3] + 1 * 3 = 3 = dirección de registro de origen 3

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

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

0 * [3] + 1 * 3 = 3 = dirección de registro de origen 3

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

La instrucción COPY indirecta

Probablemente la más útil de las instrucciones agregadas sea COPY. De hecho, Elgot-Robinson (1964) proporciona a sus modelos P ₀ y P ' ₀ las instrucciones COPY, y Cook-Reckhow (1973) proporciona a su modelo basado en acumuladores sólo dos instrucciones indirectas: COPY al acumulador indirectamente, COPY del acumulador indirectamente .

Una plétora de instrucciones : debido a que cualquier instrucción que actúe en un solo registro puede aumentarse con su "dual" indirecto (incluidos los saltos condicionales e incondicionales, véase el modelo de Elgot-Robinson), la inclusión de instrucciones indirectas duplicará el número de parámetros individuales / registrar instrucciones (por ejemplo, INC (d, r), INC (i, r)). Peor aún, cada instrucción de dos parámetros / registro tendrá 4 variedades posibles, por ejemplo:

CPY (d, r _s , d, r _d ) = COPIAR directamente desde el registro de origen directamente al registro de destino

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

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

CPY (i, r _sp , i, r _dp ) = COPIAR indirectamente el contenido del registro de origen con la dirección que se encontrará en el registro de puntero de origen r _sp , en el registro de destino con la dirección que se encontrará en el registro de 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

rendirá:

• AÑADIR (d, r _s1 , d, r _s2 , d, r _d )
• AÑADIR (i, r _sp1 , d, r _s2 , d, r _d )
• AÑADIR (d, r _s1 , i, r _sp2 , d, r _d )
• AÑADIR (i, r _sp1 , i, r _sp2 , d, r _d )
• AÑADIR (d, r _s1 , d, r _s2 , i, r _dp )
• AÑADIR (i, r _sp1 , d, r _s2 , i, r _dp )
• AÑADIR (d, r _s1 , i, r _sp2 , i, r _dp )
• AÑADIR (i, r _sp1 , i, r _sp2 , i, r _dp )

Si designamos un registro para que sea el "acumulador" (ver más abajo) y colocamos fuertes restricciones en las diversas instrucciones permitidas, entonces podemos reducir en gran medida la plétora de operaciones directas e indirectas. Sin embargo, uno debe estar seguro de que el conjunto de instrucciones reducido resultante es suficiente, y debemos ser conscientes de que la reducción vendrá a expensas de más 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 agregarlo al que ya está en él, que también puede limpiar su contenido y que puede almacenar lo que contiene. llamar acumulador a dicho órgano . En principio, es bastante convencional en las máquinas informáticas pasadas y presentes de los tipos más variados, por ejemplo, multiplicadores de escritorio, contadores estándar de IBM, máquinas de relé más modernas, el ENIAC "(negrita en el original: Goldstine y von Neumann , 1946; p. 98 en Bell y Newell 1971).

Sin embargo, el acumulador viene a expensas de más instrucciones por "operación" aritmética, en particular con respecto a las llamadas instrucciones de "lectura-modificación-escritura" como "Incrementar indirectamente el contenido del registro apuntado por el registro r2". "A" designa el registro "acumulador" A:

Etiqueta	Instrucción		A	r2	r378,426	Descripción
			. . .	378,426	17
INCi (r2):	CPY (i, r2, d, A)		17	378,426	17	El contenido de r2 apunta a r378,426 con contenido "17": cópielo en A
	INC (A)		18	378,426	17	Contenido de incienso de A
	CPY (d, A, i, r2)		18	378,426	18	El contenido de r2 apunta a r378,426: copie el contenido de A en r378,426

Si nos quedamos con 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 que se llame al 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, lo que ha sucedido es que estas dos instrucciones CPY han recibido nombres distintivos; sin embargo, no existe ninguna convención. La tradición (por ejemplo , la computadora MIX imaginaria de Knuth (1973) ) usa dos nombres llamados LOAD y STORE. Aquí estamos agregando 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 acumuladores tendrá todas sus operaciones aritméticas y constantes de dos variables (por ejemplo, ADD (A, r), SUB (A, r)) use (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)) requieren solo el acumulador. Ambos tipos de instrucción depositan 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 elegimos, podemos abreviar los mnemónicos porque al menos un registro de origen y el registro de destino es siempre el acumulador A. Así 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 direcciones indirectas "N"

Si nuestro modelo tiene un acumulador ilimitado, ¿podemos vincular todos los demás registros? No hasta que proporcionemos al menos un registro ilimitado del que derivamos nuestras direcciones indirectas.

El enfoque minimalista es usarlo a sí mismo (Schönhage hace esto).

Otro enfoque (Schönhage también hace esto) es declarar un registro específico como el "registro de dirección indirecta" y confinar la indirección relativa a este registro (el modelo RAM0 de Schonhage usa registros A y N tanto para instrucciones indirectas como directas). Nuevamente, nuestro nuevo registro no tiene un nombre convencional, tal vez "N" de "iNdex", o "iNdirect" o "número de dirección".

Para una máxima flexibilidad, como hemos hecho para el acumulador A, consideraremos N simplemente otro registro sujeto a incremento, decremento, borrado, prueba, copia directa, etc. Nuevamente podemos reducir la instrucción a un solo parámetro que proporcione dirección e indirección, por ejemplo.

LDAN (i / d) = CPY (i / d, N, d, A); Acumulador de carga a través de registro iNdirection

STAN (i / d) = CPY (d, A, i / d, N). Acumulador de almacenamiento mediante registro iNdirection

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

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

Schönhage hace esto para producir su conjunto de instrucciones RAM0. Consulte 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 indirecto N, por ejemplo, r = {r0, r1, r2, ...} a una cadena ilimitada de casilleros de capacidad (muy) acotada. Estos no harán nada más que contener números (muy) acotados, por ejemplo, un bit solitario con valor {0, 1}. Asimismo, encogemos el acumulador a un solo bit. Restringimos cualquier 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}

Empujamos más 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, PRINT, i, N), CLR (N), INC (N), DEC (N), JZ (i, N, I _z ), JZ ( I _z ), H}

Cambie el nombre de las instrucciones de COPY y llame a INC (N) = RIGHT, DEC (N) = LEFT y tenemos las mismas instrucciones que la máquina Post-Turing, más un CLRN adicional:

{BORRAR, IMPRIMIR, CLRN, 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 una capacidad de direccionamiento indirecto ilimitado produce una máquina Post-Turing . La máquina Post-Turing es equivalente a Turing, por lo que hemos demostrado que la RAM con direccionamiento indirecto es equivalente a Turing.

Damos aquí una demostración un poco más formal. Comience diseñando nuestro modelo con tres registros reservados "E", "P" y "N", más 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 "la cabeza" está observando actualmente. Se puede pensar que la "cabeza" está en el salto condicional; observe que usa direccionamiento indirecto (cfr. Elgot-Robinson p. 398). A medida que disminuimos o incrementamos "N", la cabeza (aparente) se "moverá a la izquierda" o "derecha" a lo largo de los cuadrados. Moviremos el contenido de "E" = 0 o "P" = 1 al "cuadrado escaneado" como apunta N, usando el CPY indirecto.

The fact that our tape is left-ended presents us with a minor problem: Whenever LEFT occurs our instructions will have to test to determine whether or not the contents of "N" is zero; if so we should leave its count at "0" (this is our choice as designers – for example we might have the machine/model "trigger an event" of our choosing).

Instruction set 1 (augmented): { INC (N), DEC (N), CLR (N), CPY (d, r_s,i, N), JZ ( i, r, z ), HALT }

The following table both defines the Post-Turing instructions in terms of their RAM equivalent instructions and gives an example of their functioning. The (apparent)location of the head along the tape of registers r0-r5 . . . is shown shaded:

Mnemonic	label:			E	P	N		r0	r1	r2	r3	r4	r5	etc.	Action on registers	Action on finite state machine Instruction Register IR
	start:			0	1	3					1	0
R	right:	INC ( N )		0	1	4					1	0			[N] +1 → N	[IR] +1 → IR
P	print:	CPY ( d, P, i, N )		0	1	4					1	1			[P]=1 → [N]=r4	[IR] +1 → IR
E	erase:	CPY ( d, E, i, N )		0	1	4					1	0			[E]=0 → [N]=r4	[IR] +1 → IR
L	left:	JZ ( i, N, end )		0	1	4					1	0			none	IF N =r4] =0 THEN "end" → IR else [IR]+1 → IR
		DEC ( N )		0	1	3					1	0			[N] -1 → N
J0 ( halt )	jump_if_blank:	JZ ( i, N, end )		0	1	3					1	0			none	IF N =r3] =0 THEN "end" → IR else [IR]+1 → IR
J1 ( halt )	jump_if_mark:	JZ ( i, N, halt )		0	1	3					1	0			N =r3] → A	IF N =r3] =0 THEN "end" → IR else [IR]+1 → IR
	end	. . . etc.		0	1	3					1	0
	halt:	H		0	1	3					1	0			none	[IR] +1 → IR

Example: Bounded indirection yields a machine that is not Turing equivalent

Throughout this demonstration we have to keep in mind that the instructions in the finite state machine's TABLE is bounded, i.e. finite:

"Besides a merely being a finite set of rules which gives a sequence of operations for solving a specific type of problem, an algorithm has five important features [Finiteness, Definiteness, Input, Output, Effectiveness]" (italics added, Knuth p. 4-7).

The difficulty arises because the registers have explicit "names" (numbers) and our machine must call each out by name in order to "access" it.

We will build the indirect CPY ( i, q, d, φ ) with the CASE operator. The address of the target register will be specified by the contents of register "q"; once the CASE operator has determined what this number is, CPY will directly deposit the contents of the register with that number into register "φ". We will need an additional register that we will call "y" – it serves as an up-counter.

So the following is actually a constructive demonstration or proof that we can indeed simulate the indirect CPY ( i, q, d, φ ) without a "hardware" design change to our counter machine/model. However, note that because this indirect CPY is "bounded" by the size/extent of the finite state machine, a RASP using this indirect CPY can only calculate the primitive recursive functions, not the full suite of mu recursive functions.

The CASE "operator" is described in Kleene (1952) (p. 229) and in Boolos-Burgess-Jeffrey (2002) (p. 74); the latter authors emphasize its utility. The following definition is per Kleene but modified to reflect the familiar "IF-THEN-ELSE" construction.

The CASE operator "returns" a natural number into φ depending on which "case" is satisfied, starting with "case_0" and going successively through "case_last"; if no case is satisfied then the number called "default" (aka "woops") is returned into φ (here x designates some selection of parameters, e.g. register q and the string r0, ... rlast )):

Definition by cases φ (x, y):

• case_0: IF Q₀(x, y) is true THEN φ₀(x, y) ELSE
• case_1: IF Q₁(x, y) is true THEN φ₁(x, y) ELSE
• cases_2 through case_next_to_last: etc. . . . . . . . . ELSE
• case_last: IF Q_last(x, y) is true THEN φ_last(x, y) ELSE
• default: do φ_default(x, y)

Kleene require that the "predicates" Q_n that doing the testing are all mutually exclusive – "predicates" are functions that produce only { true, false } for output; Boolos-Burgess-Jeffrey add the requirement that the cases are "exhaustive".

We begin with a number in register q that represents the address of the target register. But what is this number? The "predicates" will test it to find out, one trial after another: JE (q, y, z) followed by INC (y). Once the number is identified explicitly, the CASE operator directly/explicitly copies the contents of this register to φ:

Definition by cases CPY (i, q, d, φ) =_def φ (q, r0, ..., rlast, y) =

• case_0: IF CLR (y), [q] - [y]=0 THEN CPY ( r0, φ ), J (exit) ELSE
• case_1: IF INC (y), [q] = [y]=1 THEN CPY ( r1, φ ), J (exit) ELSE
• case_2 through case n: IF . . . THEN . . . ELSE
• case_n: IF INC (y), [q] = [y]=n THEN CPY ( rn, φ ), J (exit) ELSE
• case_n+1 to case_last: IF . . . THEN . . . ELSE
• case_last: IF INC (y), [q] = [y]="last" THEN CPY ( rlast, φ ), J (exit) ELSE
• default: woops

Case_0 ( the base step of the recursion on y) looks like this:

• case_0:

• CLR ( y ) ; set register y = 0
• JE ( q, y, _φ0 )
• J ( case_1 )

• _φ0: CPY ( r0, φ )
• J ( exit )

• case_1: etc.

Case_n (the induction step) looks like this; remember, each instance of "n", "n+1", ..., "last" must be an explicit natural number:

• case_n:

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

• _φn: CPY ( rn, φ )
• J ( exit )

• case__n+1: etc.

Case_last stops the induction and bounds the CASE operator (and thereby bounds the "indirect copy" operator):

• case_last:

• INC ( y )
• JE ( q, y, _φlast )
• J ( woops )

• _φlast: CPY ( rlast, φ )
• J ( exit )

• woops: how do we handle an out-of-bounds attempt?
• exit: etc.

If the CASE could continue ad infinitum it would be the mu operator. But it can't – its finite state machine's "state register" has reached its maximum count (e.g. 65365 = 11111111,11111111₂ ) or its table has run out of instructions; it is a finite machine, after all.

Examples of models

Register-to-register ("read-modify-write") model of Cook and Reckhow (1973)

The commonly encountered Cook and Rechkow model is a bit like the ternary-register Malzek model (written with Knuth mnemonics – the original instructions had no mnemonics excepting TRA, Read, Print).

• LOAD ( C, rd ) ; C → rd, C is any integer

Example: LOAD ( 0, 5 ) will clear register 5.

• ADD ( rs1, rs2, rd ) ; [rs1] + [rs2] → rd, the registers can be the same or different;

Example: ADD ( A, A, A ) will double the contents of register A.

• SUB ( rs1, rs2, rd ) ; [rs1] - [rs2] → rd, the registers can be the same or different:

Example: SUB ( 3, 3, 3 ) will clear register 3.

• COPY ( i, rp, d, rd ) ; [[rp] ] → rd, Indirectly copy the contents of the source-register pointed to by pointer-register r_p into the destination register.
• COPY ( d, rs, i, rp ) ; [rs] → [rp]. Copy the contents of source register r_s into the destination-register pointed to by the pointer-register r_p.
• JNZ ( r, Iz ) ; Conditional jump if [r] is positive; i.e. IF [r] > 0 THEN jump to instruction z else continue in sequence (Cook and Reckhow call this: "TRAnsfer control to line m if Xj > 0")
• READ ( rd ) ; copy "the input" into destination register r_d
• PRINT ( rs ) ; copy the contents of source register r_s to "the output."

Schönhage's RAM0 and RAM1 (1980)

Schönhage (1980) describes a very primitive, atomized model chosen for his proof of the equivalence of his SMM pointer machine model:

"In order to avoid any explicit addressing the RAM0 has the accumulator with contents z and an additional address register with current contents n (initially 0)" (p. 494)

RAM1 model: Schönhage demonstrates how his construction can be used to form the more common, usable form of "successor"-like RAM (using this article's mnemonics):

• LDA k ; k --> A , k is a constant, an explicit number such as "47"
• LDA ( d, r ) ; [r] → A ; directly load A
• LDA ( i, r ) ; [[r]] → A ; indirectly load A
• STA ( d, r ) ; [A] → r ; directly store A
• STA ( i, r ) ; [A] → [r] ; indirectly store A
• JEA ( r, z ) ; IF [A] = [r] then Iz else continue
• INCA ; [A] + 1 --> A

RAM0 model: Schönhage's RAM0 machine has 6 instructions indicated by a single letter (the 6th "C xxx" seems to involve 'skip over next parameter'. Schönhage designated the accumulator with "z", "N" with "n", etc. Rather than Schönhage's mnemonics we will use the mnemonics developed above.

• (Z), CLRA: 0 → A
• (A), INCA: [A] +1 → A
• (N), CPYAN: [A] → N
• (A), LDAA: [[A]] → A ; contents of A points to register address; put register's contents into A
• (S), STAN: [A] → [N] ; contents of N points to register address; put contents of A into register pointed to by N
• (C), JAZ ( z ): [A] = 0 then go to Iz ; ambiguous in his treatment

Indirection comes (i) from CPYAN (copy/transfer contents A to N) working with store_A_via_N STAN, and from (ii) the peculiar indirection instruction LDAA ( [[A]] → [A] ).

Footnotes

Finite vs unbounded

The definitional fact that any sort of counter machine without an unbounded register-"address" register must specify a register "r" by name indicates that the model requires "r" to be finite, although it is "unbounded" in the sense that the model implies no upper limit to the number of registers necessary to do its job(s). For example, we do not require r < 83,617,563,821,029,283,746 nor r < 2^1,000,001, etc.

Thus our model can "expand" the number of registers, if necessary to perform a certain computation. However this does mean that whatever number the model expands to must be finite – it must be indexable with a natural number: ω is not an option.

We can escape this restriction by providing an unbounded register to provide the address of the register that specifies an indirect address.

See also

• Real RAM
• Transdichotomous model

External links

• Random Access Machine Emulator
• Random Access Machine Emulator

References

With a few exceptions, these references are the same as those at Register machine.

• • Goldstine, Herman H., and von Neumann, John, "Planning and Coding of the Problems for an Electronic Computing Instrument", Rep. 1947, Institute for Advanced Study, Princeton. Reprinted on pp. 92–119 in Bell, C. Gordon and Newell, Allen (1971), Computer Structures: Readings and Examples, McGraw-Hill Book Company, New York. ISBN 0-07-004357-4}.
• George Boolos, John P. Burgess, Richard Jeffrey (2002), Computability and Logic: Fourth Edition, Cambridge University Press, Cambridge, England. The original Boolos-Jeffrey text has been extensively revised by Burgess: more advanced than an introductory textbook. "Abacus machine" model is extensively developed in Chapter 5 Abacus Computability; it is one of three models extensively treated and compared – the Turing machine (still in Boolos' original 4-tuple form) and recursion the other two.
• Arthur Burks, Herman Goldstine, John von Neumann (1946), Preliminary discussion of the logical design of an electronic computing instrument, reprinted pp. 92ff in Gordon Bell and Allen Newell (1971), Computer Structures: Readings and Examples, mcGraw-Hill Book Company, New York. ISBN 0-07-004357-4 .
• Stephen A. Cook and Robert A. Reckhow (1973), Time-bounded random access machines, Journal of Computer Systems Science 7(4):354-375.
• Martin Davis (1958), Computability & Unsolvability, McGraw-Hill Book Company, Inc. New York.
• Calvin Elgot and Abraham Robinson (1964), Random-Access Stored-Program Machines, an Approach to Programming Languages, Journal of the Association for Computing Machinery, Vol. 11, No. 4 (October, 1964), pp. 365–399.
• J. Hartmanis (1971), "Computational Complexity of Random Access Stored Program Machines," Mathematical Systems Theory 5, 3 (1971) pp. 232–245.
• John Hopcroft, Jeffrey Ullman (1979). Introduction to Automata Theory, Languages and Computation, 1st ed., Reading Mass: Addison-Wesley. ISBN 0-201-02988-X. A difficult book centered around the issues of machine-interpretation of "languages", NP-Completeness, etc.
• Stephen Kleene (1952), Introduction to Metamathematics, North-Holland Publishing Company, Amsterdam, Netherlands. ISBN 0-7204-2103-9.
• Donald Knuth (1968), The Art of Computer Programming, Second Edition 1973, Addison-Wesley, Reading, Massachusetts. Cf pages 462-463 where he defines "a new kind of abstract machine or 'automaton' which deals with linked structures."
• Joachim Lambek (1961, received 15 June 1961), How to Program an Infinite Abacus, Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 295-302. In his Appendix II, Lambek proposes a "formal definition of 'program'. He references Melzak (1961) and Kleene (1952) Introduction to Metamathematics.
• Z. A. Melzak (1961, received 15 May 1961), An informal Arithmetical Approach to Computability and Computation, Canadian Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 279-293. Melzak offers no references but acknowledges "the benefit of conversations with Drs. R. Hamming, D. McIlroy and V. Vyssots of the Bell telephone Laborators and with Dr. H. Wang of Oxford University."
• Marvin Minsky (1961, received August 15, 1960). "Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines". Annals of Mathematics. The Annals of Mathematics, Vol. 74, No. 3. 74 (3): 437–455. doi:10.2307/1970290. JSTOR 1970290.
• Marvin Minsky (1967). Computation: Finite and Infinite Machines (1st ed.). Englewood Cliffs, N. J.: Prentice-Hall, Inc. In particular see chapter 11: Models Similar to Digital Computers and chapter 14: Very Simple Bases for Computability. In the former chapter he defines "Program machines" and in the later chapter he discusses "Universal Program machines with Two Registers" and "...with one register", etc.
• John C. Shepherdson and H. E. Sturgis (1961) received December 1961 Computability of Recursive Functions, Journal of the Association of Computing Machinery (JACM) 10:217-255, 1963. An extremely valuable reference paper. In their Appendix A the authors cite 4 others with reference to "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, A. P. On operator algorithms, (Russian) Dok. Akad. Nauk 122 (1958), 967-970. English translation, 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 (Göttingen) 4 (1954), 42-53.

• Arnold Schönhage (1980), Storage Modification Machines, Society for Industrial and Applied Mathematics, SIAM J. Comput. Vol. 9, No. 3, August 1980. Wherein Schōnhage shows the equivalence of his SMM with the "successor RAM" (Random Access Machine), etc. resp. Storage Modification Machines, in Theoretical Computer Science (1979), pp. 36–37
• Peter van Emde Boas, "Machine Models and Simulations" pp. 3–66, in: Jan van Leeuwen, ed. Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity, The MIT PRESS/Elsevier, 1990. ISBN 0-444-88071-2 (volume A). QA 76.H279 1990. van Emde Boas's treatment of SMMs appears on pp. 32–35. This treatment clarifies Schōnhage 1980 – it closely follows but expands slightly the Schōnhage treatment. Both references may be needed for effective understanding.
• Hao Wang (1957), A Variant to Turing's Theory of Computing Machines, JACM (Journal of the Association for Computing Machinery) 4; 63-92. Presented at the meeting of the Association, June 23–25, 1954.