stringtranslate.com

Registrar maquina

En lógica matemática e informática teórica , una máquina de registro es una clase genérica de máquinas abstractas utilizadas de manera similar a una máquina de Turing . Todos los modelos de máquinas de registro son equivalentes a Turing .

Descripción general

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

Hay al menos cuatro subclases encontradas en la literatura . En orden ascendente de complejidad son:

Cualquier modelo de máquina de registro correctamente definido es equivalente a Turing . La velocidad computacional depende en gran medida de las características específicas del modelo.

En la informática práctica, ocasionalmente se emplea 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" se utiliza a veces indistintamente para describir una máquina virtual. [1]

Definicion formal

Una máquina registradora consta de:

  1. Un número ilimitado de registros etiquetados, discretos e ilimitados de extensión (capacidad) : un conjunto finito (o infinito en algunos modelos) de registros, cada uno de los cuales se considera de extensión infinita y cada uno contiene un único número entero no negativo (0, 1, 2,...). [nb 1] Los registros pueden hacer su propia aritmética, o puede haber uno o más registros especiales que hacen la aritmética, por ejemplo, un "acumulador" y/o un "registro de direcciones". Véase también Máquina de acceso aleatorio .
  2. Contadores o marcas : [nb 2] objetos o marcas discretas e indistinguibles de un solo tipo adecuado al modelo. En el modelo de máquina contadora más reducida , por cada operación aritmética sólo se añade o elimina un objeto/marca de su ubicación/cinta. En algunos modelos de máquinas contadoras (por ejemplo, Melzak, [2] Minsky [3] ) y en la mayoría de los modelos RAM y RASP se puede agregar o eliminar más de un objeto/marca en una operación con "suma" y generalmente "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 sola 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 poder 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 contadora: { Incremento (r), Decremento (r), Borrado a cero (r) } RAM reducida, RASP: { Incremento (r), Decremento ( r), Borrar a cero (r), Constante de carga inmediata k, Sumar ( ), Restar propio ( ), Incrementar acumulador, Decrementar acumulador, Borrar acumulador, Sumar el contenido del registro r al acumulador, Propio- Reste el contenido del registro r 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 bits, etc.) }
    2. Control : Modelos de máquinas contadoras: Opcionalmente incluyen { Copiar ( ) }. Modelos RAM y RASP: la mayoría incluye {Copiar ( ) }, o {Cargar acumulador desde r, almacenar acumulador en r, cargar acumulador con una constante inmediata}. Todos los modelos: incluya al menos un "salto" condicional (bifurcación, ir a) después de la prueba de un registro, como { Jump-if-zero, Jump-if-not-zero (es decir, Jump-if-positive), Jump -si-igual, Saltar-si-no-igual}. Todos los modelos incluyen opcionalmente: {salto de programa incondicional (goto)}.
    3. Método de dirección de registro :
      • 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 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 tener en cuenta que el IR no es el "contador de programas" (PC) del RASP (o computadora convencional). La PC es simplemente otro registro similar a un acumulador, pero específicamente reservado para contener el número de la instrucción actual basada en registros 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) una 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" (al que se hace referencia 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 puntero, el almacén de instrucciones está en la "TABLA" de la máquina de estados finitos; por tanto, estos modelos son ejemplos de la arquitectura de Harvard. En el caso del RASP, el almacén de programas está en los registros; por tanto, este es un ejemplo de la arquitectura de Von Neumann. Véase también Máquina de acceso aleatorio y Máquina de programa almacenado de acceso aleatorio . Por lo general, al igual que los programas de computadora , las instrucciones se enumeran en orden secuencial; a menos que un salto sea exitoso, la secuencia predeterminada continúa en orden numérico. Una excepción a esto son los modelos de máquina contadora ábaco [4] [3] : cada instrucción tiene al menos un identificador de instrucción "siguiente" "z", y la rama condicional tiene dos.
    • Observe también que el modelo del ábaco combina dos instrucciones, JZ y luego DEC: por ejemplo, {INC (r, z), JZDEC (r, z verdadero , z falso )}.
      Consulte Formalismo McCarthy para obtener más información sobre la expresión condicional "IF r=0 THEN z true ELSE z false " [5]

Desarrollo histórico del modelo de máquina registradora.

A principios de la década de 1950 aparecieron dos tendencias: la primera fue caracterizar la computadora como una máquina de Turing, la segunda fue definir modelos similares a computadoras (modelos con secuencias de instrucciones secuenciales y saltos condicionales) con el poder de una máquina de Turing, es decir, una máquina de Turing. -llamada equivalencia de Turing. La necesidad de este trabajo se llevó a cabo en el contexto de dos problemas "difíciles": el problema verbal 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 en torno a las ecuaciones diofánticas . Los investigadores buscaban modelos equivalentes a Turing que fueran de naturaleza menos "lógica" 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  [de] (1959), [10] el segundo paso con Hao Wang ( 1954, [11] 1957 [12] ) y, como se señaló anteriormente, desarrollado por Zdzislaw Alexander Melzak  [d] (1961), [2] Joachim Lambek (1961) [4] y Marvin Minsky (1961, [3] 1967 [13] ).

Los últimos cinco nombres aparecen explícitamente en ese orden por Yuri Matiyasevich . Él sigue con:

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

Lambek, Melzak, Minsky, Shepherdson y Sturgis descubrieron de forma independiente la misma idea al mismo tiempo. Consulte la nota sobre precedencia a continuación.

La historia comienza con el modelo de Wang.

Modelo de Wang (1954, 1957): máquina post-Turing

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

{ IZQUIERDA, DERECHA, IMPRIMIR, SALTAR_if_marked_to_instruction_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 del Post { JUMP_to_instrucción_z } (o a para facilitar las cosas, el salto condicional JUMP_IF_blank_to_instruction_z, o ambos. Lee nombró a este modelo "W-machine":

{ IZQUIERDA, DERECHA, IMPRIMIR, BORRAR, SALTAR_si_marcado, [tal vez SALTAR o SALTAR_SI_en blanco] }

Wang expresó su esperanza de que su modelo fuera "un acercamiento" :63  entre la teoría de las máquinas de Turing y el mundo práctico de la computadora.

El trabajo de Wang fue muy influyente. Lo encontramos referenciado 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 

Martin Davis finalmente evolucionó este modelo hasta convertirlo en la máquina Post-Turing (de dos símbolos).

Dificultades con el modelo de Wang/Post-Turing :

Excepto que había un problema: el modelo Wang (las seis instrucciones de la máquina Post-Turing de siete instrucciones) seguía siendo un dispositivo de cinta única similar a Turing, por agradable que pudiera ser el flujo secuencial de instrucciones de su programa . 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 cierta opacidad... una máquina de Turing tiene un funcionamiento (hipotético) lento y, por lo general, complicado. Esto hace que sea bastante difícil diseñarla, y aún más difícil investigar cuestiones como el tiempo o el almacenamiento optimización o comparación entre la eficiencia de dos algoritmos [2] : 281  .
"...aunque no son difíciles... las pruebas son complicadas y tediosas de seguir por dos razones: (1) Una máquina de Turing tiene sólo una cabeza, por lo que uno se ve obligado a dividir el cálculo en pasos muy pequeños de operaciones en un solo dígito (2) Tiene una sola cinta, por lo que hay que tomarse la molestia de encontrar el número con el que se desea trabajar y mantenerlo separado de otros números" [7] : 218. 

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

Los modelos de Minsky, Melzak-Lambek y Shepherdson-Sturgis "cortan la cinta" en muchos

El pensamiento 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 el extremo izquierdo, y llamar a estas tres cintas "cintas post-Turing (es decir, tipo Wang)". Los cabezales individuales se moverán hacia la izquierda (para disminuir) y hacia la derecha (para incrementar). En cierto sentido, las cabezas 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 una cabeza imprime o borra.

Se debe tener cuidado al escribir las instrucciones de modo que se produzca una prueba de cero y un salto antes de disminuir; 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 pocas como una) todavía permiten que la máquina sea equivalente a Turing si los datos de la cinta se representan como un número de Gödel ( o algún otro número codificable-decodificable de forma única); este número evolucionará a medida que avance el cálculo. En la versión de una cinta con codificación del número de Gödel , la máquina contadora debe poder (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 salta si el resto es cero. Minsky (1967) [13] muestra que la necesidad de este extraño conjunto de instrucciones puede reducirse a { INC (r), JZDEC (r, z) } y las instrucciones de conveniencia { CLR (r), J (r) } si dos Hay cintas disponibles. Sin embargo, todavía se requiere una simple Gödelización. Un resultado similar aparece en Elgot-Robinson (1964) [17] con respecto a su modelo RASP.

El modelo de Melzak (1961) es diferente: grupos de guijarros entran y salen de los agujeros.

El modelo de Melzak (1961) [2] es significativamente diferente. Tomó su propio modelo, volteó las cintas verticalmente y las llamó "agujeros en el suelo" que debían llenarse con "contadores de guijarros". A diferencia del "incremento" y "decremento" de Minsky, Melzak permitió la resta adecuada de cualquier recuento de guijarros y las "sumas" de cualquier recuento 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 incompleta 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) atomiza el modelo de Melzak en el modelo de Minsky (1961): INC y DEC-con-prueba

Lambek (1961) [4] tomó el modelo ternario de Melzak y lo atomizó en dos instrucciones unarias (X+, X− si es posible, o salte), exactamente las mismas dos que se le habían ocurrido a Minsky (1961) [3] .

Sin embargo, al igual que el modelo de Minsky (1961) [3] , el modelo de Lambek ejecuta sus instrucciones de manera secuencial por defecto: 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 tiene éxito.

Elgot-Robinson (1964) y el problema del RASP sin abordaje indirecto

Una máquina RASP o de acceso aleatorio con programa almacenado comienza como una máquina contadora con su "programa de instrucción" colocado en sus "registros". De manera análoga, pero independiente de, el "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 y operan sobre, el número de la instrucción actual. La TABLA de instrucciones de la máquina de estados finitos es responsable de (i) obtener la instrucción del programa actual del registro adecuado, (ii) analizar la instrucción del programa , (iii) obtener los operandos especificados por la instrucción del programa y (iv) ejecutar la instrucción del programa. .

Excepto que hay un problema: si esta máquina de von Neumann se basa en el chasis de la contramáquina , similar a una computadora, no será equivalente a 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) finitos . El RASP basado en una máquina contadora puede calcular cualquier función recursiva primitiva (por ejemplo, multiplicación), pero no todas las funciones recursivas (por ejemplo, la función de Ackermann ).

Elgot-Robinson investigan la posibilidad de permitir que su modelo RASP "automodifique" las instrucciones de su 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.

Ir a calculado: un programa RASP de instrucciones que modifica la "dirección de ir a" 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 (lejos) "más allá/por encima" del límite superior del registro de instrucciones de la máquina de estados finitos y la TABLA.

Ejemplo: una máquina contadora equipada con sólo cuatro registros ilimitados puede, por ejemplo, multiplicar dos números cualesquiera ( m, n ) para obtener p (y así ser una función recursiva primitiva) sin importar cuán grandes sean los números m y n; Además, ¡se necesitan menos de 20 instrucciones para hacer esto! por ejemplo, { 1: CLR ( p ), 2: JZ ( m, hecho ), 3 bucle_exterior: JZ ( n, hecho ), 4: CPY ( m, temp ), 5: bucle_interior: JZ ( m, bucle_exterior ), 6: DEC ( m ), 7: INC ( p ), 8: J ( bucle_interior ), 9: bucle_exterior: DEC ( n ), 10 J ( bucle_exterior ), DETENER }
Sin embargo, con sólo 4 registros, esta máquina no es lo suficientemente grande como para construir un RASP que pueda ejecutar el algoritmo de multiplicación como un programa . No importa qué tan grande construyamos nuestra máquina de estados finitos, siempre habrá un programa (incluidos sus parámetros) que sea más grande. Entonces, por definición, la máquina de programación acotada que no utiliza trucos de codificación ilimitada, como los números de Gödel, no puede ser universal .

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

"... la computadora del programa debe tener alguna forma de realizar un seguimiento de cuántos RPT quedan por realizar, y esto podría agotar cualquier cantidad particular de almacenamiento permitida en la parte finita de la computadora. Las operaciones de RPT requieren infinitos registros propios , en general, y deben ser tratados de manera diferente a los otros tipos de operaciones que hemos considerado". [13] : 214 

Pero Elgot y Robinson resuelven el problema: [17] Aumentan su P 0 RASP con un conjunto indexado de instrucciones, una forma algo más complicada (pero más flexible) de direccionamiento indirecto. Su modelo P' 0 aborda los registros agregando 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 máquina de estados finitos.

Hartmanis (1971)

En 1971, Hartmanis simplificó la indexación a dirección indirecta para usarla en su modelo RASP. [20]

Direccionamiento indirecto: un registro de 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 de puntero es la dirección del registro "destino" que utilizará la instrucción. Si el registro de puntero no está limitado, la RAM y un RASP adecuado integrado en su chasis serán equivalentes a Turing. El registro de destino puede servir como registro de origen o de destino, según lo especificado en 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 de puntero y luego haz xyz con él. Debe especificar explícitamente por nombre, a través de su instrucción, este registro de puntero (por ejemplo, "N", o "72" o "PC", etc.), pero no tiene que saber qué número contiene realmente el registro de puntero ( quizás 279.431).

Cook y Reckhow (1973) describen la RAM

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

Precedencia

Minsky trabajaba en el Laboratorio Lincoln del MIT y publicó allí su trabajo; su artículo se recibió 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] ( recibidos, respectivamente, mayo y 15 de junio de 1961, y publicados uno al lado del otro en septiembre de 1961). Que (i) ambos eran canadienses y estaban publicados en el Canadian Mathematical Bulletin , (ii) ninguno habría hecho 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. Melzak, lleva a plantear la hipótesis de que su trabajo se produjo de forma simultánea e independiente.

Casi exactamente lo mismo les pasó a Shepherdson y Sturgis. [21] Su artículo se recibió en diciembre de 1961, apenas unos meses después de que se recibiera el trabajo de Melzak y Lambek. Nuevamente, tuvieron poco (como máximo 1 mes) o ningún beneficio al 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 los números de accesibilidad se presentan.

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] 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:

producir 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
para "cambiar el curso de un cálculo", ya sea comparando dos números o disminuyendo hasta 0

De hecho, Shepherson y Sturgis concluyen

"Los distintos sistemas mínimos son muy similares" [7] : 246 

Por orden de fecha de publicación, los trabajos de Kaphengst (1959), [10] Ershov (1958), [22] Péter (1958) fueron los primeros. [9]

Ver también

Bibliografía

Textos de antecedentes: La siguiente bibliografía de artículos fuente incluye una serie de textos que se utilizarán como antecedentes. Las matemáticas que llevaron a la avalancha de artículos sobre máquinas abstractas en las décadas de 1950 y 1960 se pueden encontrar en van Heijenoort (1967) [23] , una recopilación 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 desde Gödel (1931) [25] hasta el postscriptum 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 amplían 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. Varios artículos hacen referencia a Kleene (1952) [29] y Davis (1958) [30] .

Para un buen tratamiento de la máquina contadora, consulte el Capítulo 11 de Minsky (1967), "Modelos similares a las computadoras digitales": él llama a la máquina contadora una "computadora de programa". [13] Una visión general reciente se encuentra en van Emde Boas (1990). [31] Un tratamiento reciente del modelo de Minsky (1961) [3] /Lambek (1961) [4] se puede encontrar en Boolos–Burgess–Jeffrey (2002); [32] reencarnan el "modelo ábaco" de Lambek para demostrar la equivalencia de las máquinas de Turing y las funciones recursivas parciales, y proporcionan una introducción a nivel de posgrado tanto a los modelos abstractos de máquinas (contra y Turing) como a las matemáticas de la teoría de la recursividad. A partir de la primera edición de Boolos-Burgess (1970) [33], este modelo apareció prácticamente con 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] se citan en Wang (1957); [12] a su vez, Melzak (1961), [2] Minsky (1961) [3] y Shepherdson-Sturgis (1961-1963) [21] [7] hacen referencia a Wang , ya que reducen de forma independiente las cintas de Turing a "contadores". ". Melzak (1961) [2] proporciona dirección indirecta a su modelo de máquina contadora de guijarros en agujeros, pero no lleva el tratamiento más lejos. El trabajo de Elgot-Robinson (1964) [17] define las RASP (máquinas de programas almacenados de acceso aleatorio similares a computadoras) y parece ser el primero en investigar la falla de la máquina de contador acotado para calcular las funciones mu-recursivas. . Este fracaso—excepto con el uso draconiano de los números de Gödel a la manera de Minsky (1961) [3] —lleva 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 los RASP con programas automodificables. Hartmanis (1971) [20] especifica un conjunto de instrucciones con dirección indirecta, citando notas de conferencias de Cook (1970). [34] Para su uso en investigaciones de complejidad computacional, Cook y su estudiante graduado Reckhow (1973) [18] proporcionan la definición de 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) y de forma independiente de Schönhage (1980). [36]

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

Todos los textos y artículos, excepto los de cuatro estrellas, han sido presenciados. 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] ofrecen 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 a Burke- Goldstine-von Neumann (1946-1947) [19] análisis de la arquitectura informática.

Notas

  1. ^ ". . . una secuencia numerable de registros numerados 1, 2, 3, ..., cada uno de los cuales puede almacenar cualquier número natural 0, 1, 2, .... Cada programa en particular, sin embargo, implica sólo un número finito de estos registros, los demás permanecen vacíos (es decir, contienen 0) durante todo el cálculo". (Shepherdson y Sturgis 1961: p. 219); (Lambek 1961: p. 295) propuso: "un conjunto infinitamente numerable de ubicaciones (agujeros, cables, etc.).
  2. ↑ Por ejemplo, (Lambek 1961: p. 295) propuso el uso de guijarros, cuentas, etc.
  3. ^ Véase la "Nota" en (Shepherdson y Sturgis 1963: p. 219). En su Apéndice A, los autores continúan con una lista y discusiones de los conjuntos de instrucciones de Kaphengst, Ershov y Péter (cf. p. 245 y siguientes).

Referencias

  1. ^ Harold Abelson y Gerald Jay Sussman con Julie Sussman, Estructura e interpretación de programas informáticos , MIT Press , Cambridge, Massachusetts , segunda edición, 1996
  2. ^ abcdefghijklmnop Melzak, Zdzislaw Alexander [en Wikidata] (septiembre de 1961). "Un enfoque aritmético informal de la computabilidad y la computación". Boletín de Matemáticas Canadiense . 4 (3): 89, 279–293 [89, 281, 288, 290–292]. doi : 10.4153/CMB-1961-031-9 .El manuscrito fue recibido por la revista el 15 de mayo de 1961. Melzak no ofrece referencias pero reconoce "el beneficio de las conversaciones con los Drs. R. Hamming, D. McIlroy y V. Vyssotsky de Bell Telephone Laboratories y con el Dr. H. Wang de Universidad de Oxford." [1]
  3. ^ abcdefghijklm Minsky, Marvin (1961). "Insolvencia recursiva del problema de la 'etiqueta' de la publicación y otros temas en la teoría de las máquinas de Turing". Anales de Matemáticas . 74 (3): 437–455 [438, 449]. doi :10.2307/1970290. JSTOR  1970290.
  4. ^ abcdef Lambek, Joachim (septiembre de 1961). "Cómo programar un ábaco infinito". Boletín de Matemáticas Canadiense . 4 (3): 295–302 [295]. doi : 10.4153/CMB-1961-032-6 .El manuscrito fue recibido por la revista el 15 de junio de 1961. 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 .
  5. ^ McCarthy (1960)
  6. ^ abcd Emil Post (1936)
  7. ^ abcdefghijklm Shepherdson, Sturgis (1963): John C. Shepherdson y HE Sturgis (1961) recibieron en diciembre de 1961 "Computabilidad de funciones recursivas", Revista de la Asociación de Maquinaria de Computación (JACM) 10:217–255 [218, 219, 245ff , 246], 1963. Un artículo de referencia extremadamente valioso. En su Apéndice A, los autores citan otros 4 con referencia a "Minimidad de instrucciones utilizadas en 4.1: Comparación con sistemas similares".
  8. ^ ab Hans Hermes "Die Universalität programmgesteuerter Rechenmaschinen". Matemáticas-Física. Semesterberichte (Göttingen) 4 (1954), 42–53.
  9. ^ abcde Péter, Rózsa "Graphschemata und rekursive Funktionen", Dialectica 12 (1958), 373.
  10. ^ abcdef Kaphengst, Heinz  [de] , "Eine Abstrakte Programmgesteuerte Rechenmaschine", Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 5 (1959), 366–379. [2]
  11. ^ ab Hao Wang "Variante de la teoría de las máquinas informáticas de Turing". Presentado en la reunión de la Asociación del 23 al 25 de junio de 1954.
  12. ^ abcde 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 de Computación ) 4; 63–92. Presentado en la reunión de la Asociación del 23 al 25 de junio de 1954.
  13. ^ abcdefg Minsky, Marvin (1967). Computación: máquinas finitas e infinitas (1ª ed.). Englewood Cliffs, Nueva Jersey, EE. UU.: Prentice-Hall, Inc. p. 214.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.
  14. ↑ Yuri Matiyasevich , El décimo problema de Hilbert , comentario al capítulo 5 del libro, en http://logic.pdmi.ras.ru/yumat/H10Pbook/commch_5htm.)
  15. ^ CY Lee (1961)
  16. ^ 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 , págs. 171 y siguientes. Un libro difícil centrado en las cuestiones de la interpretación automática de "lenguajes", la integridad NP, etc. 
  17. ^ abcdefg Calvin Elgot y Abraham Robinson (1964), "Máquinas de programas almacenados de acceso aleatorio, un enfoque de 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.
  18. ^ abcd Stephen A. Cook y Robert A. Reckhow (1972), Máquinas de acceso aleatorio con límite de tiempo , Journal of Computer Systems Science 7 (1973), 354–375.
  19. ^ abc Arthur Burks , Herman Goldstine , John von Neumann (1946-1947), "Discusión preliminar sobre el diseño lógico de un instrumento informático electrónico", reimpreso págs. 92 y siguientes en Gordon Bell y Allen Newell (1971), Estructuras informáticas: lecturas y Ejemplos , McGraw-Hill Book Company, Nueva York. ISBN 0-07-004357-4 . 
  20. ^ abcde Juris 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.
  21. ^ abc Shepherdson, Sturgis (1961), pág. 219
  22. ^ abcd Ershov, Andrey P. "Sobre algoritmos de operador", (ruso) Dok. Akád. Nauk 122 (1958), 967–970. Traducción al inglés, Automat. Expreso 1 (1959), 20-23.
  23. ^ ab van Heijenoort (1967)
  24. ^ Frege (1879)
  25. ^ ab Gödel (1931)
  26. ^ ab Davis (ed.) Lo indecidible (1965)
  27. ^ Gödel (1964), posdata p. 71.
  28. ^ ab Turing (1936)
  29. ^ abcde Stephen Kleene (1952), Introducción a las metamatemáticas , North-Holland Publishing Company, Ámsterdam, Países Bajos. ISBN 0-7204-2103-9 . 
  30. ^ abc Martin Davis (1958), Computabilidad e insolubilidad , McGraw-Hill Book Company, Inc. Nueva York.
  31. ^ ab Peter van Emde Boas , "Modelos y simulaciones de máquinas", 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 que hace van Emde Boas de los SMM aparece en las páginas 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 efectiva. 
  32. ^ abc George Boolos , John P. Burgess , Richard Jeffrey (2002), Computabilidad y lógica: cuarta edición , Cambridge University Press, Cambridge, Inglaterra. Burgess ha revisado exhaustivamente el texto original de Boolos-Jeffrey: es más avanzado que un libro de texto introductorio. El modelo de "máquina ábaco" se desarrolla ampliamente en el Capítulo 5 Computabilidad del ábaco ; es uno de los tres modelos ampliamente tratados y comparados: la máquina de Turing (aún en la forma original de 4 tuplas de Boolos) y la recursividad los otros dos.
  33. ^ ab George Boolos , John P. Burgess (1970)
  34. ^ Cocinero (1970)
  35. ^ ab 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 vinculadas".
  36. ^ ab 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 la "RAM sucesora" (Random Access Machine), etc. resp. Máquinas de modificación de almacenamiento , en Informática teórica (1979), págs. 36–37

Otras lecturas

enlaces externos

Wikimedia Commons tiene medios relacionados con Registrar máquinas .