Máquina contadora

Una máquina contadora o autómata contador es una máquina abstracta utilizada en lógica formal e informática teórica para modelar la computación . Es el tipo más primitivo de las cuatro máquinas de registro . Una máquina contadora consta de un conjunto de uno o más registros ilimitados , cada uno de los cuales puede almacenar un único entero no negativo, y una lista de instrucciones aritméticas y de control (generalmente secuenciales) que la máquina debe seguir. La máquina contadora se utiliza típicamente en el proceso de diseño de algoritmos paralelos en relación con el principio de exclusión mutua. Cuando se utiliza de esta manera, la máquina contadora se utiliza para modelar los pasos de tiempo discretos de un sistema computacional en relación con los accesos a la memoria. Al modelar los cálculos en relación con los accesos a la memoria para cada paso computacional respectivo, los algoritmos paralelos pueden diseñarse de tal manera que se evite el enclavamiento, la operación de escritura simultánea por dos (o más) hilos en la misma dirección de memoria .

Las máquinas con tres contadores pueden calcular cualquier función recursiva parcial de una sola variable. Las máquinas con dos contadores son Turing completas : pueden simular cualquier máquina de Turing codificada adecuadamente. Las máquinas con un solo contador pueden reconocer un superconjunto propio de los lenguajes regulares y un subconjunto de los lenguajes deterministas libres de contexto . ^{[ 1 ]}

Para un modelo de contador dado, el conjunto de instrucciones es minúsculo : de una a seis o siete instrucciones. La mayoría de los modelos contienen algunas operaciones aritméticas y al menos una operación condicional (si la condición es verdadera, se realiza un salto). Tres modelos base , cada uno con tres instrucciones, se extraen de la siguiente colección. (Las abreviaturas son arbitrarias).

• CLR (r): Borra el registro r . (Establece r a cero).
• INC (r): Incrementa el contenido del registro r .
• DEC (r): DECrementa el contenido del registro r .
• CPY (r _j , r _k ): Copia el contenido del registro r _j al registro r _k dejando intacto el contenido de r _j .
• JZ (r, z): SI el registro r contiene cero ENTONCES salta a la instrucción z SINO continúa en secuencia.
• JE (r _j , r _k , z): SI el contenido del registro r _j es igual al contenido del registro r _k ENTONCES salta a la instrucción z SINO continúa en secuencia.

Además, una máquina suele tener una instrucción HALT, que detiene la máquina (normalmente después de que se haya calculado el resultado).

Utilizando las instrucciones mencionadas anteriormente, varios autores han analizado ciertas máquinas contadoras:

• Conjunto 1: { INC (r), DEC (r), JZ (r, z) }, (Minsky (1961, 1967), Lambek (1961))
• conjunto 2: { CLR (r), INC (r), JE (r _j , r _k , z) }, (Ershov (1958), Peter (1958) según la interpretación de Shepherdson–Sturgis (1964); Minsky (1967); Schönhage (1980))
• conjunto 3: {INC (r), CPY (r _j , r _k ), JE (r _j , r _k , z)}, (Elgot-Robinson (1964), Minsky (1967))

Los tres modelos base de máquinas contadoras tienen la misma capacidad de cálculo, ya que las instrucciones de un modelo se derivan de las de otro. Todas son equivalentes a la capacidad de cálculo de las máquinas de Turing . Debido a su procesamiento unario, las máquinas contadoras suelen ser exponencialmente más lentas que las máquinas de Turing comparables.

Los modelos de máquinas contadoras reciben diferentes nombres que pueden ayudar a distinguirlas por sus peculiaridades. A continuación, la instrucción "JZDEC ( r )" es una instrucción compuesta que comprueba si un registro r está vacío; si lo está, salta a la instrucción I _z , de lo contrario, decrementa el contenido de r:

• Máquina de Minsky , porque Marvin Minsky (1961) formalizó el modelo. Máquina de ábaco , el nombre que Lambek (1961) dio a su simplificación del modelo de Melzak (1961), y como Boolos–Burgess–Jeffrey (1974) la llaman. Máquina de Lambek , un nombre alternativo que Boolos–Burgess–Jeffrey (1974) dio a la máquina de ábaco. Normalmente usa el conjunto de instrucciones (1), pero la ejecución de instrucciones no es secuencial por defecto, por lo que el parámetro adicional 'z' aparece para especificar la siguiente instrucción después de INC y como alternativa en JZDEC:

  { INC ( r, z ), JZDEC ( r, z _verdadero , z _falso ) }

• Máquina de programa , computadora de programa , los nombres que Minsky (1967) le dio al modelo porque, como una computadora, sus instrucciones proceden secuencialmente a menos que un salto condicional sea exitoso. Utiliza (generalmente) el conjunto de instrucciones (1), pero puede ampliarse de manera similar al modelo de Shepherson-Sturgis. JZDEC a menudo se divide en:

  { INC ( r ), CPY ( r _s , r _d ), JZ ( r, z _verdadero )}

• Máquina sucesora , porque utiliza la "operación sucesora" de los axiomas de Peano y se asemeja mucho a ellos . Se utiliza como base para el modelo RAM sucesor . Utiliza el conjunto de instrucciones (2) de, por ejemplo, Schönhage como base para sus modelos RAM0 y RAM1 que conducen a su modelo de máquina de punteros SMM, ^{[ 2 ] [ 3 ]} también discutido brevemente por Van Emde Boas: ^{[ 4 ] [ 5 ]}

  { CLR ( r ), INC ( r ), JE ( r _j , r _k , z ) }

• El modelo de Elgot-Robinson se utilizó para definir su modelo RASP (1964). Este modelo requiere un registro vacío al inicio (por ejemplo, [r0] = 0). (Ampliaron el mismo modelo con direccionamiento indirecto mediante el uso de un registro adicional que funciona como registro de "índice").

  { INC (r), CPY ( r _s , r _d ), JE ( r _j , r _k , z ) }

• Máquina de Shepherdson-Sturgis , porque estos autores expusieron formalmente su modelo en una exposición de fácil acceso (1963). Utiliza el conjunto de instrucciones (1) aumentado con instrucciones de conveniencia adicionales (JNZ es "Saltar si no es cero", utilizado en lugar de JZ):

  { INC ( r ), DEC ( r ), CLR ( r ), CPY ( r _j , r _k ), JNZ ( r, z ), J ( z ) }

• Otras máquinas contadoras : Minsky (1967) demuestra cómo construir los tres modelos base (programa/Minsky/Lambek-ábaco, sucesor y Elgot-Robinson) a partir del superconjunto de instrucciones disponibles descrito en el primer párrafo de este artículo. El modelo de Melzak (1961) es bastante diferente del anterior porque incluye 'sumar' y 'restar' en lugar de 'incrementar' y 'decrementar'. Las pruebas de Minsky (1961, 1967) de que un solo registro bastará para la equivalencia de Turing requieren las dos instrucciones {MULtiply k y DIV k} para codificar y decodificar el número de Gödel en el registro que representa el cálculo. Minsky muestra que si hay dos o más registros disponibles, entonces las instrucciones más simples INC, DEC, etc., son adecuadas (pero el número de Gödel sigue siendo necesario para demostrar la equivalencia de Turing ; también demostrado en Elgot-Robinson 1964).

Una máquina contadora consta de:

1. Registros de valores enteros no acotados etiquetados : un conjunto finito (o infinito en algunos modelos) de registros r₀ ... rₙ _{, cada uno de los cuales puede almacenar cualquier entero no negativo (0, 1, 2, ..., es decir ,} no acotado). Los registros realizan sus propias operaciones aritméticas; puede haber uno o más registros especiales, por ejemplo, el "acumulador" (véase Máquina de acceso aleatorio para más información).  
2. Un registro de estado que almacena/identifica la instrucción actual que se va a ejecutar. Este registro es finito y está separado de los registros superiores; por lo tanto, el modelo de máquina de contador es un ejemplo de la arquitectura de Harvard.
3. Lista de instrucciones secuenciales etiquetadas : Una lista finita de instrucciones I ₀  ... I _m . El almacenamiento del programa (instrucciones de la máquina de estados finitos ) no se encuentra en el mismo "espacio" físico que los registros. Por lo general, aunque no siempre, al igual que en los programas informáticos , las instrucciones se enumeran en orden secuencial; a menos que un salto sea exitoso, la secuencia predeterminada continúa en orden numérico. Cada una de las instrucciones de la lista pertenece a un conjunto (muy) pequeño, pero este conjunto no incluye indirección. Históricamente, la mayoría de los modelos extraían sus instrucciones de este conjunto: 

{ Incrementar (r), Decrementar (r), Borrar (r); Copiar (r _j ,r _k ), Salto condicional si el contenido de r=0, Salto condicional si r _j =r _k , Salto incondicional, DETENER }

Algunos modelos han atomizado aún más algunas de las instrucciones anteriores en instrucciones sin parámetros, o las han combinado en una sola instrucción, como "Decremento", precedida por la instrucción condicional de salto si es cero "JZ ( r, z )". La atomización de las instrucciones o la inclusión de instrucciones de conveniencia no altera la potencia conceptual, ya que cualquier programa en una variante puede traducirse directamente a la otra.

En el suplemento "Modelos de máquinas de registro" se analizan conjuntos de instrucciones alternativos .

Este ejemplo muestra cómo crear tres instrucciones más útiles: borrar , salto incondicional y copiar .

• CLR ( j ): Borra el contenido del registro r _j a cero.
• J ( z ): Saltar incondicionalmente a la instrucción I _z .
• CPY ( s, d ): Copia el contenido del registro de origen r _s al registro de destino r _d . (Véase Computadora de un conjunto de instrucciones#Arquitectura activada por transporte )

Posteriormente, r _s contendrá su recuento original (a diferencia de MOVE, que vacía el registro de origen, es decir, lo pone a cero).

El conjunto básico (1) se utiliza tal como se define aquí:

El ejemplo anterior demuestra cómo las primeras instrucciones básicas { INC, DEC, JZ } pueden generar tres instrucciones adicionales: salto incondicional J, CLR y CPY. En cierto modo, CPY utilizó tanto CLR como J, además del conjunto base. Si el registro n.° 3 hubiera tenido contenido inicialmente, la suma del contenido de los registros n.° 2 y n.° 3 habría terminado en el registro n.° 3. Por lo tanto, para ser completamente preciso, el programa CPY debería haber precedido sus movimientos con CLR (1) y CLR (3).

Sin embargo, vemos que la función ADD habría sido posible fácilmente. De hecho, a continuación se resume cómo pueden surgir las funciones recursivas primitivas como ADD, MULtiply y EXPonent. ^{[ 6 ]}

• Conjunto de instrucciones inicial: { DEC, INC, JZ, H }
• Defina el salto incondicional "J (z)" en términos de JZ ( r0, z ) dado que r0 contiene 0.

{ J, DEC, INC, JZ, H }

• Defina "CLeaR ( r ) en términos de lo anterior:

{ CLR, J, DEC, INC, JZ, H }

• Defina "CoPY ( r _j , r _k )" mientras se conserva el contenido de r _j en términos de lo anterior:

{ CPY, CLR, J, DEC, INC, JZ, H }

Lo anterior corresponde al conjunto de instrucciones de Shepherdson-Sturgis (1963).

• Defina "ADD ( r _j , r _k , r _i )", (quizás conservando el contenido de r _j , y r _k ), utilizando lo anterior:

{ ADD, CPY, CLR, J, DEC, INC, JZ, H }

• Defina "MULtiply ( r _j , r _k , r _i )" (MUL) (quizás conservando el contenido de r _j , r _k ), en términos de lo anterior:

{ MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H }

• Defina "EXPonencial ( r _j , r _k , r _i )" (EXP) (quizás conservando el contenido de r _j , r _k ) en términos de lo anterior,

{ EXP, MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H }

En general, podemos construir cualquier función recursiva primitiva, parcial o total , que deseemos, utilizando los mismos métodos. De hecho, Minsky (1967), Shepherdson-Sturgis (1963) y Boolos-Burgess-Jeffrey (1974) ofrecen demostraciones de cómo formar los cinco "operadores" de funciones recursivas primitivas (1-5 a continuación) a partir del conjunto base (1).

Pero ¿qué ocurre con la equivalencia de Turing completa ? Necesitamos añadir el sexto operador —el operador μ— para obtener la equivalencia completa, capaz de crear las funciones recursivas totales y parciales :

1. Función cero (o función constante )
2. Función sucesora
3. función identidad
4. Función de composición
5. Recursión primitiva (inducción)
6. Operador μ (operador de búsqueda no acotada)

Los autores muestran que esto se hace fácilmente dentro de cualquiera de los conjuntos base disponibles (1, 2 o 3) (un ejemplo se puede encontrar en el operador μ ). Esto significa que cualquier función recursiva mu puede implementarse como una máquina de contadores, ^{[ 7 ]} a pesar del conjunto de instrucciones finito y el tamaño del programa del diseño de la máquina de contadores. Sin embargo, la construcción requerida puede ser contraintuitiva, incluso para funciones que son relativamente fáciles de definir en máquinas de registros más complejas como la máquina de acceso aleatorio . Esto se debe a que el operador μ puede iterar un número ilimitado de veces, pero cualquier máquina de contadores dada no puede direccionar un número ilimitado de registros distintos debido al tamaño finito de su lista de instrucciones.

Por ejemplo, la jerarquía anterior de operadores recursivos primitivos se puede extender aún más allá de la exponenciación en operaciones de flecha de orden superior en la notación de flecha hacia arriba de Knuth . Para cualquier fijo${\displaystyle k}$, la función${\displaystyle Q(x,y)=x\uparrow ^{k}y}$es recursivo primitivo y puede implementarse como una máquina contadora de forma sencilla. Pero la función${\displaystyle R(n,x,y)=x\uparrow ^{n}y}$no es recursivo primitivo. Uno podría verse tentado a implementar el operador de flecha hacia arriba.${\displaystyle R}$utilizando una construcción similar a las instrucciones de sucesor, suma, multiplicación y exponenciación anteriores, implementando una pila de llamadas para que la función pueda aplicarse recursivamente a valores más pequeños de${\displaystyle n}$Esta idea es similar a cómo se podría implementar la función en la práctica en muchos lenguajes de programación. Sin embargo, la máquina de contador no puede usar un número ilimitado de registros en su cálculo, lo cual sería necesario para implementar una pila de llamadas que puede crecer arbitrariamente. La operación de flecha hacia arriba aún puede implementarse como una máquina de contador, ya que es mu recursiva; sin embargo, la función se implementaría codificando una cantidad ilimitada de información dentro de un número finito de registros, como por ejemplo usando la numeración de Gödel .

Los problemas se analizan en detalle en el artículo Máquina de acceso aleatorio . Los problemas se dividen en dos clases principales y una tercera clase de "inconvenientes":

(1) Capacidades ilimitadas de los registros frente a capacidades limitadas de las instrucciones de la máquina de estados: ¿Cómo creará la máquina constantes mayores que la capacidad de su máquina de estados finitos?

(2) Número ilimitado de registros frente a número limitado de instrucciones de la máquina de estados: ¿Cómo accederá la máquina a los registros con números de dirección que están más allá del alcance/capacidad de su máquina de estados finitos?

(3) Los modelos totalmente reducidos son engorrosos:

Shepherdson y Sturgis (1963) no se disculpan por su conjunto de 6 instrucciones. Tomaron su decisión basándose en la "facilidad de programación... en lugar de la economía" (pág.  219, nota al pie 1).

Instrucciones de Shepherdson y Sturgis ([r] indica "contenido del registro r"):

• • INCREMENTO ( r )  ; [r] +1 → r
  • DECREMENTO ( r )  ; [r] -1 → r
  • BORRAR ( r )  ; 0 → r
  • COPIAR ( r _s a r _d )  ; [r _s ] → r _d
  • SALTO INCONDICIONAL a la instrucción I _z
  • SALTAR SI [r] = 0 a la instrucción I _z

Minsky (1967) amplió su conjunto de 2 instrucciones { INC (z), JZDEC (r, I _z ) } a { CLR (r), INC (r), JZDEC (r, I _z ), J (I _z ) } antes de su prueba de que una "Máquina de Programa Universal" puede construirse con solo dos registros (pág.  255 y ss.).

Para cada máquina de Turing , existe una máquina de dos contadores (2CM) que la simula, siempre que la entrada y la salida de la 2CM estén codificadas correctamente. Esto se demuestra en el libro de Minsky ( Computation , 1967, pp.  255-258), y a continuación se esboza una demostración alternativa en tres pasos. Primero, una máquina de Turing puede ser simulada por una máquina de estados finitos (FSM) equipada con dos pilas. Luego, dos pilas pueden ser simuladas por cuatro contadores. Finalmente, cuatro contadores pueden ser simulados por dos contadores. La máquina de dos contadores utiliza el conjunto de instrucciones { INC ( r, z ), JZDEC ( r, z _verdadero , z _falso ) }.

La calculadora Friden EC-130 no tenía lógica de sumador propiamente dicha. Su lógica era altamente serial, realizando operaciones aritméticas mediante conteo. Internamente, los dígitos decimales eran de base 1; por ejemplo, un seis se representaba con seis pulsos consecutivos dentro del intervalo de tiempo asignado a ese dígito. Cada intervalo de tiempo contenía un dígito, comenzando por el menos significativo. Los acarreos activaban un biestable que sumaba un conteo al dígito en el siguiente intervalo de tiempo.

Las sumas se realizaban mediante un contador ascendente, mientras que las restas se realizaban mediante un contador descendente, con un esquema similar para gestionar los préstamos.

El esquema de ranuras de tiempo definía seis registros de 13 dígitos decimales, cada uno con un bit de signo . La multiplicación y la división se realizaban básicamente mediante sumas y restas repetidas. La versión de raíz cuadrada , la EC-132, restaba efectivamente enteros impares consecutivos, requiriendo cada decremento dos restas consecutivas. Después de la primera, el minuendo se incrementaba en uno antes de la segunda resta.

• Modelo de máquina contadora
• Computadora con un conjunto de instrucciones
• Máquina de punteros
• Máquina post-Turing
• Máquina de acceso aleatorio
• Máquina registradora
• Máquina Wang B
• Sistema de adición vectorial

• Boolos, George ; Burgess, John P.; Jeffrey , Richard (2007) [1974]. Computabilidad y lógica (5.ª  ed.). Cambridge, Inglaterra: Cambridge University Press . doi : 10.1017/CBO9780511804076 . ISBN 9780521877527.El texto original de Boolos y Jeffrey ha sido revisado exhaustivamente por Burgess: es más avanzado que un libro de texto introductorio. El modelo de la "máquina de ábaco" se desarrolla ampliamente en el Capítulo 5, Computabilidad del ábaco ; es uno de los tres modelos que se tratan y comparan en profundidad: la máquina de Turing (aún en la forma original de 4-tuplas de Boolos) y la recursión son los otros dos.

• Burks, Arthur ; Goldstine, Herman ; Von Neumann, John (1946). Discusión preliminar del diseño lógico de un instrumento de cálculo electrónico ., reimpreso en Bell, Gordon ; Newell, Allen, eds. (1971) [1946]. Estructuras informáticas: lecturas y ejemplos . Nueva York: McGraw-Hill Book Company. ISBN 0-07-004357-4.
• Cook, Stephen A. ; Reckhow, Robert A. (1973). "Máquinas de acceso aleatorio con límite de tiempo" (PDF) . Journal of Computer and System Sciences . 7 (4): 354– 375. doi : 10.1016/S0022-0000(73)80029-7 .
• Davis, Martin (1958). Computabilidad e insolubilidad . Nueva York: McGraw-Hill Book Company, Inc.
• Elgot, Calvin; Robinson, Abraham (1964). "Máquinas de programas almacenados de acceso aleatorio, un enfoque para los lenguajes de programación". Journal of the Association for Computing Machinery . 11 (4): 365– 399. doi : 10.1145/321239.321240 .
• Fischer, Patrick C.; Meyer , Albert R .; Rosenberg, Arnold L. (1968), "Máquinas contadoras y lenguajes contadores", Mathematical Systems Theory , 2 (3): 265– 283, doi : 10.1007/bf01694011 , MR 0235932 , S2CID 13006433  Desarrolla teoremas de jerarquía temporal y jerarquía espacial para máquinas de contadores, análogos a las jerarquías para máquinas de Turing.
• Hartmanis, Juris (1971). "Complejidad computacional de las máquinas de programas almacenados de acceso aleatorio". Teoría de sistemas matemáticos . 5 (3): 232– 245. doi : 10.1007/BF01694180 .
• Hopcroft, John ; Ullman, Jeffrey (1979). Introducción a la teoría de autómatas, lenguajes y computación (1.ª  ed.). Reading, Massachusetts: Addison-Wesley. ISBN 0-201-02988-X.Un libro complejo que gira en torno a cuestiones como la interpretación automática de "lenguajes", la NP-completitud, etc.
• Hopcroft, John ; Motwani, Rajeev ; Ullman, Jeffrey (2003) [1979]. Introducción a la teoría de autómatas, lenguajes y computación (2.ª  ed.). Reading, Massachusetts: Addison-Wesley. pág.  352. ISBN 0-201-44124-1.
• Kleene, Stephen (1952). Introducción a la metamatemática . Ámsterdam, Países Bajos: North-Holland Publishing Company. ISBN 0-7204-2103-9.{{cite book}}: Incompatibilidad de ISBN/Fecha ( ayuda )
• Knuth, Donald (1973) [1968]. El arte de la programación informática (2.ª  ed.). Reading, Massachusetts: Addison-Wesley.Cf páginas 462-463 donde define "un nuevo tipo de máquina abstracta o 'autómata' que se ocupa de estructuras enlazadas.
• Lambek, Joachim (1961). "Cómo programar un ábaco infinito". Boletín Matemático . 4 (3): 295– 302. doi : 10.4153/CMB-1961-032-6 .En su Apéndice II, Lambek propone una "definición formal de 'programa'". Hace referencia a Melzak (1961) y Kleene (1952) Introducción a la metamatemática .
• Melzak, ZA (1961). "Un enfoque aritmético informal de la computabilidad y la computación". Boletín Matemático Canadiense . 4 (3): 279– 293. doi : 10.4153/CMB-1961-031-9 .Melzak no ofrece referencias, pero reconoce "el beneficio de las conversaciones con los doctores R. Hamming, D. McIlroy y V. Vyssots de los Laboratorios Bell Telephone y con el Dr. H. Wang de la Universidad de Oxford".
• Minsky, Marvin (1961). "Recursive Unsolvability of Post's Problem of "Tag" and Other Topics in Theory of Turing Machines". Annals of Mathematics . 74 (3): 437– 455. doi : 10.2307/1970290 . JSTOR 1970290 . 
• Minsky, Marvin (1967). Computación: Máquinas finitas e infinitas (1.ª  ed.). Englewood Cliffs, NJ: Prentice-Hall, Inc.En particular, véanse los capítulos 11: Modelos similares a las computadoras digitales y 14: Bases muy simples para la computabilidad . En el primer capítulo define las "máquinas de programa" y en el segundo analiza las "máquinas de programa universales con dos registros" y "...con un registro", etc.
• Shepherdson, JC ; Sturgis, HE (1963). "Computabilidad de funciones recursivas" . Journal of the Association for Computing Machinery . 10 (2): 217– 255. doi : 10.1145/321160.321170 .Un valioso documento de referencia. En su Apéndice A, los autores citan otros 4 con referencia a "Minimalidad de las instrucciones utilizadas en 4.1: comparación con sistemas similares.
  • Kaphengst, Heinz (1959). "Eine Abstrakte programmgesteuerte Rechenmaschine". Zeitschrift für mathematische Logik und Grundlagen der Mathematik . 5 ( 14– 24): 366– 379. doi : 10.1002/malq.19590051413 .
  • Ershov, AP (1958). "Sobre algoritmos de operador" . Doklady Akademii Nauk SSSR (en ruso). 122 (6): 967–970 .Traducción al inglés, Automat. Express 1 (1959), 20-23.
  • Peter, Rózsa (1958). "Esquemas gráficos y funciones recursivas" . Dialéctica (en alemán). 12 ( 3– 4): 373– 393. doi : 10.1111/j.1746-8361.1958.tb01470.x .
  • Hermes, Hans (1954). "Die Universalität programmgesteuerter Rechenmaschinen". Matemáticas-Física. Semestreberichte . 4 . Gotinga: 42– 53.
• Schönhage, Arnold (diciembre de 1973). Simulación en tiempo real de máquinas de Turing multidimensionales mediante máquinas de modificación de almacenamiento (Memorándum técnico). Cambridge, MA: Proyecto MAC del MIT. hdl : 1721.1/148866 .
• Schönhage, Arnold (1980). "Máquinas de modificación de almacenamiento". SIAM J. Comput . 9 (3). Sociedad de Matemáticas Industriales y Aplicadas: 366– 379. doi : 10.1137/0209036 .En el que Schönhage muestra la equivalencia de su SMM con la "RAM sucesora" (Máquina de Acceso Aleatorio), etc.
• Schroeppel, Rich (1972). "Una máquina de dos contadores no puede calcular 2 ^N " (PDF) . Instituto Tecnológico de Massachusetts, Laboratorio de IA, Memorando de Inteligencia Artificial n.° 257.El autor hace referencia a Minsky 1967 y señala que " Frances Yao demostró de forma independiente la no computabilidad utilizando un método similar en abril de 1971.
• van Emde Boas, Peter (1989). Modelos y simulaciones de máquinas (PDF) (Informe técnico). Teoría de la computación y la complejidad (CT). Instituto de lógica, lenguaje y computación, Universidad de Ámsterdam . Recuperado el 27 de julio de 2025 .
• van Emde Boas, Peter (1990). «Modelos y simulaciones de máquinas». En Van Leeuwen, Jan (ed.). Manual de informática teórica. Volumen A: Algoritmos y complejidad (1.ª  ed.). The MIT Press/Elsevier. pp. 3–66 . ISBN  9780444880710.El análisis de Van Emde Boas sobre los SMM aparece en las páginas  32-35. Este análisis aclara el trabajo de Schōnhage (1980): lo sigue de cerca, pero lo amplía ligeramente. Ambas referencias pueden ser necesarias para una comprensión efectiva.
• Wang, Hao (1957). "Una variante de la teoría de las máquinas de computación de Turing". Journal of the ACM . 4 : 63–92 . doi : 10.1145/320856.320867 .Presentado en la reunión de la Asociación, del 23 al 25 de junio de 1954.

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

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