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:
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:
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:
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:
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):
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".
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.
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:
Pero Elgot y Robinson resuelven el problema: [17] amplían su RASP P 0 con un conjunto de instrucciones indexadas, una forma algo más complicada (pero más flexible) de direccionamiento indirecto. Su modelo P' 0 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 :
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:
De hecho, Shepherson y Sturgis concluyen:
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] .
