Registrar máquina

En lógica matemática y ciencias de la computación teóricas , una máquina de registros es una clase genérica de máquinas abstractas , análoga a una máquina de Turing y, por lo tanto, Turing completa . A diferencia de una máquina de Turing que utiliza una cinta y un cabezal, una máquina de registros utiliza múltiples registros con direcciones únicas para almacenar números enteros no negativos. Existen varias subclases de máquinas de registros, incluidas las máquinas contadoras , las máquinas de punteros , las máquinas de acceso aleatorio (RAM) y las máquinas de programas almacenados de acceso aleatorio (RASP) , cada una de ellas con una complejidad variable. Estas máquinas, particularmente en estudios teóricos, ayudan a comprender los procesos computacionales. El concepto de máquinas de registros también se puede aplicar a las máquinas virtuales en la informática práctica, con fines educativos y para reducir la dependencia de arquitecturas de hardware específicas.

La máquina de registros recibe su nombre de su uso de uno o más " registros ". A diferencia de la cinta y el cabezal que utiliza una máquina de Turing , el modelo utiliza múltiples registros con direcciones únicas , cada uno de los cuales contiene un único entero no negativo .

En la literatura se encuentran al menos cuatro subclases , en orden ascendente de complejidad:

• Máquina contadora : el modelo teórico más primitivo y reducido del hardware informático. Esta máquina carece de direccionamiento indirecto y las instrucciones se encuentran en la máquina de estados finitos, al estilo de la arquitectura Harvard .
• Máquina de punteros : una combinación de los modelos de máquina contadora y RAM, con menos frecuencia y más abstracto que ambos modelos. Las instrucciones se encuentran en la máquina de estados finitos, al estilo de la arquitectura de Harvard.
• Máquina de acceso aleatorio (RAM): máquina contadora con direccionamiento indirecto y, por lo general, un conjunto de instrucciones ampliado. Las instrucciones se encuentran en la máquina de estados finitos, al estilo de la arquitectura Harvard.
• Modelo de máquina de programa almacenado de acceso aleatorio (RASP): una RAM con instrucciones en sus registros análoga a la máquina universal de Turing , lo que la convierte en un ejemplo de la arquitectura de von Neumann . Pero a diferencia de una computadora, el modelo está idealizado con registros efectivamente infinitos (y, si se utilizan, registros especiales efectivamente infinitos, como los acumuladores ). Sin embargo, en comparación con una computadora moderna, el conjunto de instrucciones aún es reducido en número y complejidad.

Cualquier modelo de máquina de registro correctamente definido es un modelo Turing completo . La velocidad computacional depende en gran medida de las particularidades del modelo.

En la práctica informática, se emplea ocasionalmente un concepto relacionado conocido como máquina virtual para reducir la dependencia de las arquitecturas de máquinas subyacentes. Estas máquinas virtuales también se utilizan en entornos educativos. En los libros de texto, el término "máquina de registro" a veces se utiliza indistintamente para describir una máquina virtual. ^[1]

Una máquina registradora consta de:

1. Un número ilimitado de registros etiquetados, discretos, ilimitados y sin límites en extensión (capacidad) : un conjunto finito (o infinito en algunos modelos) de registros, cada uno considerado de extensión infinita y que contiene un único entero no negativo (0, 1, 2, ...). ^{[nb 1]} Los registros pueden realizar su propia aritmética, o puede haber uno o más registros especiales que realicen la aritmética (por ejemplo, un "acumulador" y/o un "registro de dirección"). Véase también Máquina de acceso aleatorio .${\displaystyle r_{0}\lpuntos r_{n}}$
2. Marcadores o contadores de conteo : ^{[nb 2]} objetos o marcas discretos e indistinguibles de un solo tipo adecuados para el modelo. En el modelo de máquina contadora más reducido , por cada operación aritmética solo se agrega o se quita un objeto/marca de su ubicación/cinta. En algunos modelos de máquinas contadoras (por ejemplo, Melzak, ^[2] Minsky ^[3] ) y la mayoría de los modelos RAM y RASP, se puede agregar o quitar más de un objeto/marca en una operación con "suma" y, por lo general, "resta"; a veces con "multiplicación" y/o "división". Algunos modelos tienen operaciones de control como "copiar" (o alternativamente: "mover", "cargar", "almacenar") que mueven "grupos" de objetos/marcas de un registro a otro en una acción.
3. Un conjunto limitado de instrucciones : las instrucciones tienden a dividirse en dos clases: aritméticas y de control. Las instrucciones se extraen de las dos clases para formar "conjuntos de instrucciones", de modo que un conjunto de instrucciones debe permitir que el modelo sea equivalente a Turing (debe ser capaz de calcular cualquier función recursiva parcial ).
   1. Aritmética : Las instrucciones aritméticas pueden operar en todos los registros o en un registro específico, como un acumulador. Normalmente, se seleccionan de los siguientes conjuntos, aunque existen excepciones: Máquina de contador: { Incrementar (r), Decrementar (r), Borrar a cero (r) } RAM reducida, RASP: { Incrementar (r), Decrementar (r), Borrar a cero (r), Cargar-constante-inmediata k, Sumar ( ), Restar adecuadamente ( ), Incrementar acumulador, Decrementar acumulador, Borrar acumulador, Sumar el contenido del registro al acumulador, Restar adecuadamente el contenido del registro del acumulador } RAM aumentada, RASP: Incluye todas las instrucciones reducidas, así como: { Multiplicar, Dividir, varias operaciones booleanas bit a bit (desplazamiento a la izquierda, prueba de bit, etc.) }.${\displaystyle r_{1},r_{2}}$${\displaystyle r_{1},r_{2}}$${\displaystyle r}$${\displaystyle r}$
   2. Control : Modelos de máquina de contador: Incluyen opcionalmente { Copy( )}. Modelos RAM y RASP: La mayoría incluyen { Copy( )}, o { Load Accumulator from , Store accumulator into , Load Accumulator with an inmediata constante}. Todos los modelos: Incluyen al menos un "salto" condicional (bifurcación, goto) después de la prueba de un registro, como { Jump-if-zero, Jump-if-not-zero (es decir, Jump-if-positive), Jump-if-equal, Jump-if-not-equal}. Todos los modelos incluyen opcionalmente: { salto de programa incondicional (goto)}.${\displaystyle r_{1},r_{2}}$${\displaystyle r_{1},r_{2}}$${\displaystyle r}$${\displaystyle r}$
   3. Método de direccionamiento de registros :
      • Máquina contadora: sin direccionamiento indirecto, operandos inmediatos posibles en modelos altamente atomizados
      • RAM y RASP: direccionamiento indirecto disponible, operandos inmediatos típicos
   4. Entrada-salida : opcional en todos los modelos
4. Registro de estado : Un registro de instrucciones (IR) especial, distinto de los registros mencionados anteriormente, almacena la instrucción actual que se va a ejecutar junto con su dirección en la tabla de instrucciones. Este registro, junto con su tabla asociada, se encuentra dentro de la máquina de estados finitos. El IR es inaccesible en todos los modelos. En el caso de RAM y RASP, para determinar la "dirección" de un registro, el modelo puede elegir (i) la dirección especificada por la tabla y almacenada temporalmente en el IR para direccionamiento directo, o (ii) el contenido del registro especificado por la instrucción en el IR para direccionamiento indirecto. Es importante señalar que el IR no es el "contador de programa" (PC) del RASP (o computadora convencional). El PC es simplemente otro registro similar a un acumulador pero específicamente reservado para almacenar el número de la instrucción basada en registro actual del RASP. Por lo tanto, un RASP posee dos registros de "instrucción/programa": (i) el IR (registro de instrucciones de la máquina de estados finitos) y (ii) un PC (contador de programa) para el programa almacenado en los registros. Además, además de la PC, un RASP también puede dedicar otro registro al "Registro de Instrucciones de Programa" (conocido con varios nombres como "PIR", "IR", "PR", etc.).
5. Lista de instrucciones etiquetadas, generalmente en orden secuencial : Una lista finita de instrucciones . En el caso de la máquina contadora, la máquina de acceso aleatorio (RAM) y la máquina de punteros, el almacén de instrucciones está en la "TABLA" de la máquina de estados finitos, por lo que estos modelos son ejemplos de la arquitectura Harvard. En el caso del RASP, el almacén de programas está en los registros, por lo que este es un ejemplo de la arquitectura de Von Neumann. Véase también Máquina de acceso aleatorio y Máquina de programas almacenados de acceso aleatorio . Las instrucciones suelen enumerarse en orden secuencial, como los programas de ordenador , a menos que un salto sea exitoso. En este caso, la secuencia predeterminada continúa en orden numérico. Una excepción a esto son los modelos de máquina contadora de ábaco ^{[4] [3]} : cada instrucción tiene al menos un identificador de instrucción "siguiente" "z", y la rama condicional tiene dos.${\displaystyle I_{1}\ldots I_{m}}$
   
   • Observe también que el modelo de ábaco combina dos instrucciones, JZ y luego DEC: por ejemplo, { INC ( r, z ), JZDEC ( r, z _verdadero , z _falso ) }.

Consulte el Formalismo McCarthy para obtener más información sobre la expresión condicional "SI r=0 ENTONCES z _verdadero DE LO CONTRARIO z _falso " ^[5]

A principios de los años 50 aparecieron dos tendencias. La primera fue caracterizar al ordenador como una máquina de Turing. La segunda fue definir modelos similares a los ordenadores (modelos con secuencias de instrucciones secuenciales y saltos condicionales) con la potencia de una máquina de Turing, la denominada equivalencia de Turing. La necesidad de este trabajo se llevó a cabo en el contexto de dos problemas "difíciles": el problema de palabras irresoluble planteado por Emil Post ^[6] (su problema de la "etiqueta") y el problema muy "difícil" de los problemas de Hilbert (la décima pregunta sobre las ecuaciones diofánticas ). Los investigadores buscaban modelos equivalentes a Turing que fueran menos "lógicos" por naturaleza y más "aritméticos". ^{[2] : 281  [7] : 218}

El primer paso hacia la caracterización de las computadoras se originó ^{[nb 3]} con Hans Hermes (1954), ^[8] Rózsa Péter (1958), ^[9] y Heinz Kaphengst (1959), ^[10] el segundo paso con Hao Wang (1954, ^[11] 1957 ^[12] ) y, como se señaló anteriormente, fue continuado por Zdzislaw Alexander Melzak (1961), ^[2] Joachim Lambek (1961) ^[4] y Marvin Minsky (1961, ^[3] 1967 ^[13] ).

Yuri Matiyasevich enumera explícitamente los últimos cinco nombres en ese orden . A continuación, dice:

" Las máquinas de registro [algunos autores utilizan "máquina de registro" como sinónimo de "contramáquina"] son ​​especialmente adecuadas para construir ecuaciones diofánticas. Al igual que las máquinas de Turing, tienen instrucciones muy primitivas y, además, tratan con números ". ^[14]

Lambek, Melzak, Minsky, Shepherdson y Sturgis descubrieron la misma idea de forma independiente y al mismo tiempo. Véase la nota sobre precedentes que aparece a continuación.

La historia comienza con el modelo de Wang.

El trabajo de Wang surgió del artículo de Emil Post (1936) ^[6] y condujo a Wang a su definición de su máquina B de Wang : un modelo computacional de máquina Post-Turing de dos símbolos con solo cuatro instrucciones atómicas:

{ IZQUIERDA, DERECHA, IMPRIMIR, SALTAR_si_está_marcado_a_la_instrucción_z }

A estos cuatro, tanto Wang (1954, ^[11] 1957 ^[12] ) como luego CY Lee (1961) ^[15] agregaron otra instrucción del conjunto Post { ERASE }, y luego un salto incondicional de Post { JUMP_to_ instruction_z } (o para facilitar las cosas, el salto condicional JUMP_IF_blank_to_instruction_z, o ambos. Lee denominó a esto un modelo de "máquina W":

{ IZQUIERDA, DERECHA, IMPRIMIR, BORRAR, SALTAR_si_está_marcado, [quizás SALTAR o SALTAR_SI_ESTÁ_EN_VACÍO] }

Wang expresó su esperanza de que su modelo sea "un acercamiento" ^entre la teoría de las máquinas de Turing y el mundo práctico de la informática.

El trabajo de Wang fue muy influyente. Lo encontramos citado por Minsky (1961) ^[3] y (1967), ^[13] Melzak (1961), ^[2] Shepherdson y Sturgis (1963). ^[7] De hecho, Shepherdson y Sturgis (1963) señalan que:

" ...hemos intentado llevar un paso más allá el 'acercamiento' entre los aspectos prácticos y teóricos de la computación sugerido por Wang " , ^{[7] : 218}

Finalmente, Martin Davis desarrolló este modelo hasta convertirlo en la máquina Post-Turing (de 2 símbolos).

Dificultades con el modelo Wang/Post–Turing :

Pero había un problema: el modelo de Wang (las seis instrucciones de la máquina Post-Turing de siete instrucciones) seguía siendo un dispositivo de tipo Turing de una sola cinta, por más bonito que pudiera ser su flujo de instrucciones de programa secuencial . Tanto Melzak (1961) ^[2] como Shepherdson y Sturgis (1963) ^[7] observaron esto (en el contexto de ciertas pruebas e investigaciones):

" ...una máquina de Turing tiene una cierta opacidad... una máquina de Turing es lenta en su funcionamiento (hipotético) y, por lo general, complicada. Esto hace que sea bastante difícil diseñarla, y aún más difícil investigar cuestiones como la optimización del tiempo o del almacenamiento o una comparación entre la eficiencia de dos algoritmos. ^{[2] : 281} "...aunque no es difícil... las demostraciones son complicadas y tediosas de seguir por dos razones: (1) Una máquina de Turing tiene sólo una cabeza, de modo que uno está obligado a descomponer el cálculo en pasos muy pequeños de operaciones sobre un solo dígito. (2) Tiene sólo una cinta, de modo que uno tiene que esforzarse un poco para encontrar el número con el que uno desea trabajar y mantenerlo separado de otros números " ^{[7] : 218}

De hecho, como lo muestran los ejemplos de la máquina de Turing , la máquina post-Turing y las funciones parciales , el trabajo puede ser "complicado".

This section's tone or style may not reflect the encyclopedic tone used on Wikipedia. See Wikipedia's guide to writing better articles for suggestions. (January 2024) (Learn how and when to remove this message)

La idea inicial lleva a "cortar la cinta" de modo que cada una sea infinitamente larga (para acomodar números enteros de cualquier tamaño) pero con extremos izquierdos. Estas tres cintas se denominan "cintas post-Turing (es decir, similares a las de Wang)". Los cabezales individuales se mueven hacia la izquierda (para decrementar) y hacia la derecha (para incrementar). En cierto sentido, los cabezales indican "la parte superior de la pila" de marcas concatenadas. O en Minsky (1961) ^[3] y Hopcroft y Ullman (1979), ^{[16] : 171ff} la cinta siempre está en blanco, excepto por una marca en el extremo izquierdo; en ningún momento un cabezal imprime o borra.

Se debe tener cuidado al escribir las instrucciones de modo que se realice una prueba de cero y un salto antes de decrementar, de lo contrario la máquina "se caerá del extremo" o "chocará contra el extremo", creando una instancia de una función parcial .

Minsky (1961) ^[3] y Shepherdson–Sturgis (1963) ^[7] demuestran que sólo unas pocas cintas —tan sólo una— permiten que la máquina sea equivalente a Turing si los datos en la cinta se representan como un número de Gödel (o algún otro número codificable-descodificable único); este número evolucionará a medida que avance el cálculo. En la versión de una cinta con codificación de número de Gödel, la máquina contadora debe ser capaz de (i) multiplicar el número de Gödel por una constante (números "2" o "3"), y (ii) dividir por una constante (números "2" o "3") y saltar si el resto es cero. Minsky (1967) ^[13] muestra que la necesidad de este extraño conjunto de instrucciones se puede relajar a { INC (r), JZDEC (r, z) } y las instrucciones de conveniencia { CLR (r), J (r) } si hay dos cintas disponibles. Sin embargo, todavía se requiere una Gödelización simple. Un resultado similar aparece en Elgot–Robinson (1964) ^[17] con respecto a su modelo RASP.

El modelo de Melzak (1961) ^[2] es significativamente diferente. Él tomó su propio modelo, giró las cintas verticalmente y las llamó "agujeros en el suelo" que se llenaban con "contadores de guijarros". A diferencia del "incremento" y "decremento" de Minsky, Melzak permitió la sustracción adecuada de cualquier cantidad de guijarros y las "sumas" de cualquier cantidad de guijarros.

Define el direccionamiento indirecto para su modelo ^{[2] : 288} y proporciona dos ejemplos de su uso; ^{[2] : 89} su "prueba" ^{[2] : 290–292} de que su modelo es equivalente a Turing es tan imprecisa que el lector no puede decir si pretendía o no que el direccionamiento indirecto fuera un requisito para la prueba.

El legado del modelo de Melzak es la simplificación de Lambek y la reaparición de sus convenciones mnemotécnicas en Cook y Reckhow 1973. ^[18]

Lambek (1961) ^[4] tomó el modelo ternario de Melzak y lo atomizó hasta dejarlo en dos instrucciones unarias (X+, X− si es posible, de lo contrario, saltar), exactamente las mismas dos que Minsky (1961) ^[3] había ideado.

Sin embargo, al igual que el modelo de Minsky (1961) ^[3] , el modelo de Lambek ejecuta sus instrucciones de manera secuencial predeterminada: tanto X+ como X− llevan el identificador de la siguiente instrucción, y X− también lleva la instrucción de salto si la prueba cero es exitosa.

Una RASP o máquina de programas almacenados de acceso aleatorio comienza como una máquina contadora con su "programa de instrucción" colocado en sus "registros". De manera análoga, pero independiente, al "Registro de instrucciones" de la máquina de estados finitos, al menos uno de los registros (apodado "contador de programa" (PC)) y uno o más registros "temporales" mantienen un registro del número de instrucción actual y operan sobre él. La TABLA de instrucciones de la máquina de estados finitos es responsable de (i) obtener la instrucción de programa actual del registro adecuado, (ii) analizar la instrucción de programa , (iii) obtener los operandos especificados por la instrucción de programa y (iv) ejecutar la instrucción de programa .

Excepto que hay un problema: si se basa en el chasis de la máquina de contadores , esta máquina de von Neumann , similar a una computadora , no será equivalente a la de Turing. No puede calcular todo lo que es computable. Intrínsecamente, el modelo está limitado por el tamaño de las instrucciones de su máquina de estados (muy) finita . El RASP basado en la máquina de contadores puede calcular cualquier función recursiva primitiva (por ejemplo, la multiplicación), pero no todas las funciones recursivas mu (por ejemplo, la función de Ackermann ).

Elgot-Robinson investiga la posibilidad de permitir que su modelo RASP "automodifique" sus instrucciones de programa. ^[17] La ​​idea era antigua, propuesta por Burks-Goldstine-von Neumann (1946-1947), ^[19] y a veces llamada "el goto calculado". Melzak (1961) ^[2] menciona específicamente el "goto calculado" por su nombre, pero en su lugar proporciona a su modelo un direccionamiento indirecto.

Goto calculado: un programa RASP de instrucciones que modifica la "dirección goto" en una instrucción de programa de salto condicional o incondicional .

Pero esto no resuelve el problema (a menos que se recurra a los números de Gödel ). Lo que se necesita es un método para obtener la dirección de una instrucción de programa que se encuentra (mucho) "más allá/por encima" del límite superior del registro de instrucciones de la máquina de estados finitos y de la TABLA.

Ejemplo: Una máquina contadora equipada con sólo cuatro registros ilimitados puede, por ejemplo, multiplicar dos números cualesquiera (m, n) juntos para obtener p—y por lo tanto ser una función recursiva primitiva—sin importar cuán grandes sean los números m y n; ¡además, se requieren menos de 20 instrucciones para hacer esto! eg { 1: CLR(p), 2: JZ(m, done), 3 outer_loop: JZ(n, done), 4: CPY(m, temp), 5: inner_loop: JZ(m, outer_loop), 6: DEC(m), 7: INC(p), 8: J(inner_loop), 9: outer_loop: DEC(n), 10 J(outer_loop), HALT } Sin embargo, con sólo 4 registros, esta máquina no es lo suficientemente grande para construir un RASP que pueda ejecutar el algoritmo de multiplicación como un programa . No importa cuán grande sea nuestra máquina de estados finitos, siempre habrá un programa (incluidos sus parámetros) que sea más grande. Por lo tanto, por definición, la máquina de programas acotados que no utiliza trucos de codificación ilimitados, como los números de Gödel, no puede ser universal .

Minsky (1967) ^[13] insinúa este problema en su investigación de una máquina contadora (a la que llama "modelos de programa informático") equipada con las instrucciones { CLR (r), INC (r) y RPT ("a" multiplicado por las instrucciones m a n) }. No nos dice cómo solucionar el problema, pero sí observa que:

" ... el programa informático debe tener alguna manera de llevar un registro de cuántas RPT quedan por realizar, y esto podría agotar cualquier cantidad particular de almacenamiento permitida en la parte finita del ordenador. Las operaciones RPT requieren registros infinitos propios, en general, y deben tratarse de manera diferente a los otros tipos de operaciones que hemos considerado " . ^{[13] : 214}

Pero Elgot y Robinson resuelven el problema: ^[17] amplían su RASP P ₀ con un conjunto de instrucciones indexadas, una forma algo más complicada (pero más flexible) de direccionamiento indirecto. Su modelo P' ₀ direcciona los registros añadiendo el contenido del registro "base" (especificado en la instrucción) al "índice" especificado explícitamente en la instrucción (o viceversa, intercambiando "base" e "índice"). Por lo tanto, las instrucciones P' _{0 indexadas tienen un parámetro más que las instrucciones P 0} no indexadas :

Ejemplo: INC (r _base , índice); la dirección efectiva será [r _base ] + índice, donde el número natural "índice" se deriva de la propia instrucción de la máquina de estados finitos.

En 1971, Hartmanis simplificó la indexación a indirección para su uso en su modelo RASP. ^[20]

Direccionamiento indirecto: un registro puntero proporciona a la máquina de estados finitos la dirección del registro de destino requerido para la instrucción. Dicho de otra manera: el contenido del registro puntero es la dirección del registro "destino" que utilizará la instrucción. Si el registro puntero no tiene límites, la RAM y un RASP adecuado integrado en su chasis serán equivalentes de Turing. El registro de destino puede servir como registro de origen o de destino, según lo especifique la instrucción.

Tenga en cuenta que la máquina de estados finitos no tiene que especificar explícitamente la dirección de este registro de destino. Simplemente le dice al resto de la máquina: "Consígueme el contenido del registro al que apunta mi registro puntero y luego haz xyz con él". Debe especificar explícitamente por nombre, a través de su instrucción, este registro puntero (por ejemplo, "N", o "72" o "PC", etc.) pero no tiene que saber qué número contiene realmente el registro puntero (quizás 279,431).

Cook y Reckhow (1973) ^[18] citan a Hartmanis (1971) ^[20] y simplifican su modelo a lo que ellos llaman una máquina de acceso aleatorio (RAM, es decir, una máquina con indirección y la arquitectura de Harvard). En cierto sentido volvemos a Melzak (1961) ^[2] pero con un modelo mucho más simple que el de Melzak.

Minsky trabajaba en el Laboratorio Lincoln del MIT y publicó su trabajo allí; su artículo fue recibido para su publicación en Annals of Mathematics el 15 de agosto de 1960, pero no se publicó hasta noviembre de 1961. ^[3] Si bien la recepción se produjo un año completo antes de que se recibiera y publicara el trabajo de Melzak ^[2] y Lambek ^[4] (recibido, respectivamente, en mayo y el 15 de junio de 1961, y publicado uno al lado del otro en septiembre de 1961). Que (i) ambos eran canadienses y publicaron en el Canadian Mathematical Bulletin , (ii) ninguno habría tenido referencia al trabajo de Minsky porque aún no se había publicado en una revista revisada por pares, pero (iii) Melzak hace referencia a Wang y Lambek a Melzak, lleva a plantear la hipótesis de que su trabajo se produjo de manera simultánea e independiente.

Casi exactamente lo mismo les ocurrió a Shepherdson y Sturgis. ^[21] Su artículo fue recibido en diciembre de 1961, apenas unos meses después de que se recibiera el trabajo de Melzak y Lambek. Una vez más, tuvieron poco (a lo sumo un mes) o ningún beneficio de revisar el trabajo de Minsky. Tuvieron cuidado de observar en las notas a pie de página que los artículos de Ershov, ^[22] Kaphengst ^[10] y Péter ^[9] habían "aparecido recientemente" ^{[21] : 219} Estos se publicaron mucho antes, pero aparecieron en idioma alemán en revistas alemanas, por lo que se presentan problemas de accesibilidad.

El artículo final de Shepherdson y Sturgis no apareció en una revista revisada por pares hasta 1963. ^[7] Y como señalan en su Apéndice A, los "sistemas" de Kaphengst (1959), ^[10] Ershov (1958), ^[22] y Péter (1958) ^[9] son ​​todos tan similares a los resultados que se obtuvieron más tarde que son indistinguibles de un conjunto de los siguientes:

produce 0 es decir 0 → n

incrementar un número, es decir n+1 → n

"es decir, de realizar las operaciones que generan los números naturales" ^{[7] : 246}

copiar un número, es decir n → m

"cambiar el curso de un cálculo", ya sea comparando dos números o decrementándolos hasta 0

De hecho, Shepherson y Sturgis concluyen:

" Los diversos sistemas mínimos son muy similares " ^{[7] : 246}

Por orden de fecha de publicación aparecieron en primer lugar los trabajos de Kaphengst (1959), ^[10] Ershov (1958), ^[22] Péter (1958). ^[9]

Textos de referencia: La siguiente bibliografía de artículos fuente incluye una serie de textos que se pueden utilizar como referencia. Las matemáticas que llevaron a la oleada de artículos sobre máquinas abstractas en los años 1950 y 1960 se pueden encontrar en van Heijenoort (1967) ^[23] —un conjunto de artículos originales que abarcan los 50 años desde Frege (1879) ^[24] hasta Gödel (1931). ^[25] Davis (ed.) The Undecidable (1965) ^[26] lleva la antorcha hacia adelante comenzando con Gödel (1931) ^[25] hasta el posdata de Gödel (1964); ^{[27] : 71} los artículos originales de Alan Turing (1936 ^[28] –1937) y Emil Post (1936) ^[6] están incluidos en The Undecidable . Las matemáticas de Church, Rosser y Kleene que aparecen como reimpresiones de artículos originales en The Undecidable se profundizan en Kleene (1952), ^[29] un texto obligatorio para cualquiera que busque una comprensión más profunda de las matemáticas detrás de las máquinas. Tanto Kleene (1952) ^[29] como Davis (1958) ^[30] son ​​referenciados en varios de los artículos.

Para un buen tratamiento de la máquina contadora, véase Minsky (1967) Capítulo 11 "Modelos similares a las computadoras digitales"; llama a la máquina contadora una "computadora de programa". ^[13] Una revisión reciente se encuentra en van Emde Boas (1990). ^[31] Un tratamiento reciente del modelo Minsky (1961) ^[3] /Lambek (1961) ^[4] se puede encontrar en Boolos–Burgess–Jeffrey (2002); ^[32] reencarnan el "modelo de ábaco" de Lambek para demostrar la equivalencia de las máquinas de Turing y las funciones recursivas parciales, y proporcionan una introducción de nivel de posgrado tanto a los modelos de máquinas abstractas (contra- y Turing-) como a las matemáticas de la teoría de la recursión. A partir de la primera edición de Boolos–Burgess (1970) ^[33], este modelo apareció con prácticamente el mismo tratamiento.

Los artículos : Los artículos comienzan con Wang (1957) ^[12] y su dramática simplificación de la máquina de Turing. Turing (1936), ^[28] Kleene (1952), ^[29] Davis (1958), ^[30] y en particular Post (1936) ^[6] son ​​citados en Wang (1957); ^[12] a su vez, Wang es referenciado por Melzak (1961), ^[2] Minsky (1961), ^[3] y Shepherdson–Sturgis (1961–1963) ^{[21] [7]} ya que reducen independientemente las cintas de Turing a "contadores". Melzak (1961) ^[2] proporciona su modelo de máquina contadora de guijarros en agujeros con indirección pero no lleva el tratamiento más allá. El trabajo de Elgot-Robinson (1964) ^[17] define las RASP (máquinas de acceso aleatorio con programas almacenados, similares a computadoras) y parece ser el primero en investigar la falla de la máquina de contadores acotados para calcular las funciones mu-recursivas. Esta falla (excepto con el uso draconiano de los números de Gödel a la manera de Minsky (1961) ^[3] ) conduce a su definición de instrucciones "indexadas" (es decir, direccionamiento indirecto) para su modelo RASP. Elgot-Robinson (1964) ^[17] y más aún Hartmanis (1971) ^[20] investigan las RASP con programas que se modifican a sí mismos. Hartmanis (1971) ^[20] especifica un conjunto de instrucciones con indirección, citando notas de clase de Cook (1970). ^[34] Para su uso en investigaciones de complejidad computacional, Cook y su estudiante de posgrado Reckhow (1973) ^[18] proporcionan la definición de una RAM (su modelo y convención mnemotécnica son similares a los de Melzak, pero no le ofrecen ninguna referencia en el artículo). Las máquinas de punteros son una rama de Knuth (1968, ^[35] 1973) e independientemente de Schönhage (1980). ^[36]

En su mayor parte, los artículos contienen matemáticas que van más allá del nivel de pregrado, en particular las funciones recursivas primitivas y las funciones recursivas mu presentadas elegantemente en Kleene (1952) ^[29] y con menos profundidad, pero útiles de todos modos, en Boolos–Burgess–Jeffrey (2002). ^[32]

Todos los textos y artículos, excepto los cuatro con asterisco, han sido consultados. Estos cuatro están escritos en alemán y aparecen como referencias en Shepherdson–Sturgis (1963) ^[7] y Elgot–Robinson (1964); ^[17] Shepherdson–Sturgis (1963) ^[7] ofrece una breve discusión de sus resultados en el Apéndice A de Shepherdson–Sturgis. La terminología de al menos un artículo (Kaphengst (1959) ^[10] parece remontarse al análisis de la arquitectura informática de Burke–Goldstine–von Neumann (1946–1947) ^[19] .

Autor	Año	Referencia	Máquina de Turing	Máquina contadora	RAM	RASPAR	Máquina de puntero	Direccionamiento indirecto	Programa automodificable
Goldstine y von Neumann	1947 [19]
Kleene	1952 [29]
Hermes	1954–1955 [8]			?
Wang	1957 [12]			pistas				pistas
Pedro	1958 [9]			?
Davis	1958 [30]
Ershov	1959 [22]			?
Capuchón	1959 [10]			?
Melzak	1961 [2]								pistas
Cordero	1961 [4]
Minsky	1961 [3]
Shepherdson y Sturgis	1963 [7]							pistas
Elgot y Robinson	1964 [17]
Davis- Indecidible	1965 [26]
de Heijenoort	1967 [23]
Minsky	1967 [13]				pistas			pistas
Knut	1968, [35] 1973
Hartmanis	1971 [20]
Cocinar y Reckhow	1973 [18]
Belleza	1980 [36]
de Emde Boas	1990 [31]
Boolos y Burgess; Boolos, Burgess y Jeffrey	1970 [33] –2002 [32]

• Wolfram, Stephen (2002). Un nuevo tipo de ciencia. Wolfram Media, Inc., págs. 97-102. ISBN 1-57955-008-8.

Wikimedia Commons alberga una categoría multimedia sobre Máquinas registradoras .

• Weisstein, Eric W. "Máquina de registro". MundoMatemático .
• Igblan - Máquinas registradoras Minsky