Máquina de acceso aleatorio - Random-access machine

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".

Definicion 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 pone 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 pondrá 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 cintas múltiples 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 estados finitos, 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 ilimitados: 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 de manera más dramática cuando se intenta usar un modelo de máquina contraria para construir un RASP que sea equivalente a Turing y, por lo tanto, 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 "Clasificació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 0  - 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 a través de los números de Gödel si lo hace (p. 395-397; en particular, la figura 2 y la 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. 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 mueve una máquina de estados 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 contadora 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 16 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 usa 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 "indirección" 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 llamadas "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 acotada 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 por lo tanto calcular la subclase de funciones recursivas primitivas  - mediante el uso de un "operador" recursivo primitivo llamado "definición por casos" (definido en Kleene (1952) p. 229 y Boolos-Burgess-Jeffrey p. 74). Esta "indirecta delimitada" 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 es así, 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 usar el desafortunado método de números 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 ss. 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én necesitará 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 0 y P ' 0 las instrucciones COPY, y Cook-Reckhow (1973) proporciona a su modelo basado en acumuladores solo 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 sobre 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 almacenar lo que contiene. llamar acumulador a dicho órgano . En principio, es bastante convencional en las máquinas de computación pasadas y presentes de los más variados tipos, 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 especificado . 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 de iNdirection
STAN (i / d) = CPY (d, A, i / d, N). Acumulador de almacenamiento a través de 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}

Turing equivalencia 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.

El hecho de que nuestra cinta esté en el extremo izquierdo nos presenta un problema menor: siempre que ocurra LEFT, nuestras instrucciones tendrán que probar para determinar si el contenido de "N" es cero o no; si es así, deberíamos dejar su recuento 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 de Post-Turing en términos de sus instrucciones equivalentes de RAM y da un ejemplo de su funcionamiento. La ubicación (aparente) de la cabeza a lo largo de la cinta de registros r0-r5. . . se muestra sombreado:

Mnemotécnico etiqueta: mi PAG norte r0 r1 r2 r3 r4 r5 etc. Acción sobre registros Acción en la máquina de estados finitos Registro de instrucciones IR
comienzo: 0 1 3 1 0
R Derecha: INC (N) 0 1 4 1 0 [N] +1 → N [IR] +1 → IR
PAG impresión: CPY (d, P, i, N) 0 1 4 1 1 [P] = 1 → [N] = r4 [IR] +1 → IR
mi borrar: CPY (d, E, i, N) 0 1 4 1 0 [E] = 0 → [N] = r4 [IR] +1 → IR
L izquierda: JZ (i, N, final) 0 1 4 1 0 ninguno SI N = r4] = 0 ENTONCES "fin" → IR si no [IR] +1 → IR
DEC (N) 0 1 3 1 0 [N] -1 → N
J0 (detener) jump_if_blank: JZ (i, N, final) 0 1 3 1 0 ninguno SI N = r3] = 0 ENTONCES "fin" → IR si no [IR] +1 → IR
J1 (detener) jump_if_mark: JZ (i, N, detener) 0 1 3 1 0 N = r3] → A SI N = r3] = 0 ENTONCES "fin" → IR si no [IR] +1 → IR
fin . . . etc. 0 1 3 1 0
detener: H 0 1 3 1 0 ninguno [IR] +1 → IR

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 da 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 agregada, Knuth p. 4 -7).
La dificultad surge porque los registros tienen "nombres" (números) explícitos y nuestra máquina debe llamar a cada uno por su nombre para "acceder" a él.

Construiremos el CPY indirecto (i, q, d, φ) con el operador CASE. La dirección del registro de destino será especificada por el contenido del registro "q"; una vez que el operador CASE ha determinado cuál es este número, CPY depositará directamente el contenido del registro con ese número en el registro "φ". Necesitaremos un registro adicional que llamaremos "y", que sirve como contador ascendente.

Así que lo siguiente es en realidad una demostración o prueba constructiva de que de hecho 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 usa 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 es por Kleene pero modificada para reflejar la construcción familiar "SI-ENTONCES-ELSE".

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

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

  • case_0: SI Q 0 ( x , y) es verdadero ENTONCES φ 0 ( x , y) ELSE
  • case_1: SI Q 1 ( x , y) es verdadero ENTONCES φ 1 ( x , y) ELSE
  • cases_2 a case_next_to_last: etc. . . . . . . . DEMÁS
  • case_last: SI Q last ( x , y) es verdadero ENTONCES φ last ( x , y) ELSE
  • predeterminado: hacer φ predeterminado ( x , y)

Kleene requiere que los "predicados" Q n que hacen la prueba sean todos mutuamente excluyentes - los "predicados" son funciones que producen solo {verdadero, falso} para la salida; Boolos-Burgess-Jeffrey añaden 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 averiguar, un ensayo tras otro: JE (q, y, z) seguido de INC (y). Una vez que el número se identifica explícitamente, el operador CASE copia directa / explícitamente el contenido de este registro a φ:

Definición por casos CPY (i, q, d, φ) = def φ (q, r0, ..., rlast, y) =
  • case_0: SI CLR (y), [q] - [y] = 0 ENTONCES CPY (r0, φ), J (salir) ELSE
  • case_1: SI INC (y), [q] = [y] = 1 ENTONCES CPY (r1, φ), J (salir) ELSE
  • caso_2 al caso n: SI. . . LUEGO . . . DEMÁS
  • case_n: SI INC (y), [q] = [y] = n ENTONCES CPY (rn, φ), J (salir) ELSE
  • case_n + 1 a case_last: IF. . . LUEGO . . . DEMÁS
  • case_last: IF INC (y), [q] = [y] = "last" THEN CPY (rlast, φ), J (exit) ELSE
  • predeterminado: woops

Case_0 (el paso base de la recursividad en y) se ve así:

  • case_0 :
  • CLR (y); establecer registro y = 0
  • JE (q, y, _φ0 )
  • J ( caso_1 )
  • _φ0: CPY (r0, φ)
  • J ( salir )
  • case_1: etc.

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

  • case_n :
  • INC (años)
  • JE (q, y, _φn )
  • J ( caso_n + 1 )
  • _φn: CPY (rn, φ)
  • J ( salir )
  • case__n + 1: etc.

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

  • case_last :
  • INC (años)
  • JE (q, y, _φúltimo )
  • J ( woops )
  • _φúltimo : CPY (rlast, φ)
  • J ( salir )
  • woops: ¿cómo manejamos un intento fuera de límites?
  • salida: etc.

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

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 comúnmente es un poco como el modelo de Malzek de registro ternario (escrito con mnemónicos de Knuth; las instrucciones originales no tenían mnemotécnicos excepto TRA, Leer, Imprimir).

  • LOAD ( C, rd ) ; C → rd, C es cualquier número entero
Ejemplo: LOAD ( 0, 5 )borrará el registro 5.
  • ADD ( rs1, rs2, rd ) ; [rs1] + [rs2] → rd, los registros pueden ser iguales o diferentes;
Ejemplo: ADD ( A, A, A )duplicará el contenido del registro A.
  • SUB ( rs1, rs2, rd ) ; [rs1] - [rs2] → rd, los registros pueden ser iguales o diferentes:
Ejemplo: SUB ( 3, 3, 3 )borrará el registro 3.
  • COPY ( i, rp, d, rd ) ; [[rp] ] → rd, Copie indirectamente el contenido del registro de origen apuntado por el registro de puntero r p en el registro de destino.
  • COPY ( d, rs, i, rp ) ; [rs] → [rp]. Copie el contenido del registro de origen r s en el registro de destino al que apunta el registro de puntero r p .
  • JNZ ( r, Iz ) ;Salto condicional si [r] es positivo; es decir, SI [r]> 0 ENTONCES salta a la instrucción z de lo contrario continúa en secuencia (Cook y Reckhow llaman a esto: "Transfiera el control a la línea m si Xj> 0")
  • READ ( rd ) ;copiar "la entrada" en el registro de destino r d
  • PRINT ( rs ) ;copie el contenido del registro fuente r s en "la salida".

RAM0 y RAM1 de Schönhage (1980)

Schönhage (1980) describe un modelo atomizado muy primitivo elegido para su prueba de la equivalencia de su modelo de máquina de puntero SMM :

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

Modelo RAM1 : Schönhage demuestra cómo su construcción puede usarse para formar la forma más común y utilizable de RAM similar a un "sucesor" (usando los mnemónicos 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 ; cargar indirectamente A
  • STA ( d, r ) ; [A] → r ; almacenar directamente A
  • STA ( i, r ) ; [A] → [r] ; almacenar indirectamente A
  • JEA ( r, z ) ; IF [A] = [r] then Iz 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 'omitir el siguiente parámetro'. Schönhage designó el acumulador con "z", "N" con "n", etc. En lugar de los mnemónicos de Schönhage, usaremos los mnemónicos desarrollados anteriormente.

  • (Z), CLRA: 0 → A
  • (A), INCA: [A] +1 → A
  • (N), CPYAN: [A] → N
  • (A), LDAA: [[A]] → A ; el contenido de A apunta a registrar la dirección; poner el contenido del registro en A
  • (S), STAN: [A] → [N] ; contenido de N puntos para registrar la dirección; poner el contenido de A en el registro apuntado por N
  • (C), JAZ ( z ): [A] = 0 then go to Iz ; ambiguo en su trato

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

Notas al pie

Finito vs ilimitado

El hecho de que cualquier tipo de máquina contador sin un registro ilimitado - registro de "dirección" debe especificar un registro "r" por su nombre indica que el modelo requiere que "r" sea finito , aunque es "ilimitado" en el sentido de que el El modelo no implica un límite superior al número de registros necesarios para realizar su (s) trabajo (s). Por ejemplo, no requerimos 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 determinado cálculo. Sin embargo, esto hace media que cualquiera que sea el número del modelo se expande a debe ser finita  - debe ser indexable con un número natural: ω no es una opción .

Podemos escapar de esta restricción proporcionando un registro ilimitado para proporcionar la dirección del registro que especifica una dirección indirecta.

Ver también

enlaces externos

Referencias

Con 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 de un instrumento de computación electrónica", Rep. 1947, Instituto de Estudios Avanzados , Princeton. Reimpreso en las págs. 92-119 en Bell, C. Gordon y Newell, Allen (1971), Computer Structures: Readings and Examples , 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-Jeffrey ha sido revisado extensamente por Burgess: más avanzado que un libro de texto introductorio. El modelo de "máquina de ábaco" se desarrolla extensamente en el Capítulo 5 Computabilidad del ábaco ; es uno de los tres modelos ampliamente tratados y comparados: la máquina de Turing (todavía en la forma original de 4 tuplas de Boolos) y la recursividad los otros dos.
  • Arthur Burks , Herman Goldstine , John von Neumann (1946), Discusión preliminar del diseño lógico de un instrumento informático electrónico , reimpreso pp. 92ff en Gordon Bell y Allen Newell (1971), Computer Structures: Readings and Examples , mcGraw-Hill Book Company, Nueva York. ISBN  0-07-004357-4 .
  • Stephen A. Cook y Robert A. Reckhow (1973), Máquinas de acceso aleatorio limitadas en el tiempo , Journal of Computer Systems Science 7 (4): 354-375.
  • Martin Davis (1958), Computability & Unsolvability , McGraw-Hill Book Company, Inc. Nueva York.
  • Calvin Elgot y Abraham Robinson (1964), Máquinas de programa almacenado de acceso aleatorio, una aproximación a los lenguajes de programación , Revista de la Asociación de Maquinaria de Computación, vol. 11, núm. 4 (octubre de 1964), págs. 365–399.
  • J. Hartmanis (1971), "Complejidad computacional de las máquinas de programas almacenados de acceso aleatorio", Teoría de sistemas matemáticos 5, 3 (1971) págs. 232–245.
  • John Hopcroft , Jeffrey Ullman (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas , 1ª ed., Reading Mass: Addison-Wesley. ISBN  0-201-02988-X . Un libro difícil centrado en los problemas de la interpretación automática de "lenguajes", NP-Completeness, etc.
  • Stephen Kleene (1952), Introducción a las metamatemáticas , North-Holland Publishing Company, Amsterdam, Países Bajos. ISBN  0-7204-2103-9 .
  • Donald Knuth (1968), El arte de la programación informática , segunda edición 1973, Addison-Wesley, Reading, Massachusetts. Cf. páginas 462-463 donde define "un nuevo tipo de máquina abstracta o 'autómata' que se ocupa de estructuras enlazadas".
  • Joachim Lambek (1961, recibido el 15 de junio de 1961), Cómo programar un ábaco infinito , Boletín matemático, vol. 4, no. 3. Septiembre de 1961 páginas 295-302. En su Apéndice II, Lambek propone una "definición formal de 'programa'. Hace referencia a Melzak (1961) y Kleene (1952) Introducción a las metamatemáticas .
  • ZA Melzak (1961, recibido el 15 de mayo de 1961), Un enfoque aritmético informal a la computabilidad y la computación , Canadian Mathematical Bulletin , vol. 4, no. 3. Septiembre de 1961 páginas 279-293. Melzak no ofrece referencias, pero reconoce "el beneficio de las conversaciones con los doctores R. Hamming, D. McIlroy y V. Vyssots de los Bell Telephone Laborators y con el Dr. H. Wang de la Universidad de Oxford".
  • Marvin Minsky (1961). "Inestabilidad recursiva del problema de Post de 'etiqueta' y otros temas en la teoría de las máquinas de Turing". Annals of Mathematics . The Annals of Mathematics, vol. 74, núm. 3. 74 (3): 437–455. doi : 10.2307 / 1970290 . JSTOR  1970290 .
  • Marvin Minsky (1967). Computación: máquinas finitas e infinitas (1ª ed.). Englewood Cliffs, Nueva Jersey: Prentice-Hall, Inc.En particular, consulte el capítulo 11: Modelos similares a las computadoras digitales y el capítulo 14: Bases muy simples para la computabilidad . En el capítulo anterior define "Máquinas de programa" y en el capítulo posterior analiza "Máquinas de programa universal con dos registros" y "... con un registro", etc.
  • John C. Shepherdson y HE Sturgis (1961) recibieron en diciembre de 1961 Computability of Recursive Functions , Journal of the Association of Computing Machinery (JACM) 10: 217-255, 1963. Un artículo de referencia extremadamente valioso. En su Apéndice A, los autores citan otros 4 con referencia a "Mínimo de instrucciones utilizadas en 4.1: Comparación con sistemas similares".
  • Kaphengst, Heinz, Eine Abstrakte programmgesteuerte Rechenmaschine ' , Zeitschrift für Mathische Logik und Grundlagen der Mathematik: 5 (1959), 366-379.
  • Ershov, AP Sobre algoritmos de operador , (ruso) Dok. Akad. Nauk 122 (1958), 967-970. Traducción al inglés, Automat. Express 1 (1959), 20-23.
  • Péter, Rózsa Graphschemata und rekursive Funktionen , Dialectica 12 (1958), 373.
  • Hermes, Hans Die Universalität programmgesteuerter Rechenmaschinen. Math.-Phys. Semsterberichte (Gotinga) 4 (1954), 42-53.
  • Arnold Schönhage (1980), Máquinas de modificación de almacenamiento , Sociedad de Matemáticas Industriales y Aplicadas, SIAM J. Comput. Vol. 9, No. 3, agosto de 1980. Donde Schōnhage muestra la equivalencia de su SMM con el "sucesor RAM" (Random Access Machine), etc. resp. Storage Modification Machines , en Theoretical Computer Science (1979), págs. 36-37
  • Peter van Emde Boas , "Modelos de máquinas y simulaciones" 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 tratamiento de van Emde Boas de los SMM aparece en las págs. 32–35. Este tratamiento aclara Schōnhage 1980: sigue de cerca pero amplía ligeramente el tratamiento de Schōnhage. Es posible que se necesiten ambas referencias para una comprensión eficaz.
  • Hao Wang (1957), una variante de la teoría de las máquinas informáticas de Turing , JACM (Revista de la Asociación de Maquinaria Informática) 4; 63-92. Presentado en la reunión de la Asociación, 23-25 ​​de junio de 1954.