Modelo de máquina contadora

Shepherdson y Sturgis (1963) observan que "la prueba de esta universalidad [de las computadoras digitales a las máquinas de Turing]... parece haber sido escrita por primera vez por Hermes, quien mostró en [7--su número de referencia] cómo una computadora idealizada podría programarse para duplicar el comportamiento de cualquier máquina de Turing" , y: "El enfoque de Kaphengst es interesante porque da una prueba directa de la universalidad de las computadoras digitales actuales, al menos cuando se idealizan hasta el punto de admitir una infinidad de registros de almacenamiento, cada uno capaz de almacenar palabras arbitrariamente largas" . ^{[ 1 ]}

Las únicas dos instrucciones aritméticas son:

1. Operación sucesora
2. Probar dos números para ver si son iguales

El resto de las operaciones son transferencias de registro a acumulador o de acumulador a registro, o saltos de prueba.

El artículo de Kaphengst está escrito en alemán; la traducción de Sheperdson y Sturgis utiliza términos como "molino" y "órdenes".

La máquina contiene un acumulador. Kaphengst designa su acumulador con el símbolo de infinito, pero en la descripción siguiente utilizaremos la letra "A". También contiene un registro de órdenes ("orden" como instrucción, no como secuencia). (Este uso proviene de la descripción de un instrumento de cálculo electrónico que aparece en el informe de Burks, Goldstine y von Neumann (1946)). El registro de órdenes/instrucciones es el registro "0". Y, aunque no queda claro en la exposición de Sheperdson y Sturgis, el modelo contiene un registro de extensión designado por Kaphengst como "infinito primo"; utilizaremos la letra "E".

Las instrucciones se almacenan en los registros:

"...así que la máquina, como una computadora real, es capaz de realizar operaciones aritméticas en su propio programa" (p. 244).

Por lo tanto, este modelo es en realidad una máquina de acceso aleatorio . En lo que sigue, "[ r ]" indica el "contenido del" registro r, etc.

Shepherdson y Sturgis (1963) eliminan el molino/acumulador A y reducen las instrucciones de Kaphengst a "copiar" entre registros, "incrementar" y "comparar" entre registros. Nótese que no hay decremento . Este modelo, casi idéntico, se encuentra en Minsky (1967) ; véase más información en la sección siguiente.

Shepherdson y Sturgis (1963) observan que el modelo de Ersov permite almacenar el programa en los registros. Afirman que el modelo de Ersov es el siguiente:

Shepherdson y Sturgis (1963) observan que el "tratamiento" de Péter (no son muy específicos al respecto) tiene una equivalencia con las instrucciones que se muestran en la siguiente tabla. Comentan específicamente sobre estas instrucciones, que:

"Desde el punto de vista de demostrar lo más rápidamente posible la computabilidad de todas las funciones recursivas parciales, la de Péter es quizás la mejor; para demostrar su computabilidad mediante máquinas de Turing es necesario un análisis adicional de la operación de copia siguiendo las líneas que hemos tomado anteriormente." ^{[ 2 ]}

En su investigación sobre los problemas de Emil Post (el sistema de etiquetas ) y el décimo problema de Hilbert ( los problemas de Hilbert , la ecuación diofántica ), Minsky llegó a la siguiente definición de:

"una base interesante para la teoría de funciones recursivas que involucra programas de solo las operaciones aritméticas más simples". ^{[ 3 ]}

Su "Teorema Ia" afirma que cualquier función recursiva parcial está representada por "un programa que opera sobre dos enteros S1 y S2 usando instrucciones Ij de las formas: ^{[ 4 ]}

El primer teorema es el contexto de un segundo "Teorema IIa" que

"...representa cualquier función recursiva parcial mediante un programa que opera sobre un entero S [contenido en un único registro r1] utilizando instrucciones I _j de las formas":

En esta segunda forma, la máquina utiliza números de Gödel para procesar "el entero S". Afirma que la primera máquina/modelo no necesita hacer esto si dispone de 4 registros.

"Nuestro objetivo es describir un dispositivo primitivo, al que llamaremos máquina Q, que logra una computabilidad efectiva mediante la aritmética en lugar de la lógica. Sus tres operaciones son llevar la cuenta, comparar enteros no negativos y transferir" (Melzak (1961), p.  281).

Si utilizamos el contexto de su modelo, "llevar la cuenta" significa "sumar en incrementos sucesivos" (como lanzar una piedrecita) o "restar en decrementos sucesivos"; transferir significa mover (no copiar) el contenido del agujero A al agujero B, y comparar números es evidente. Esto parece ser una combinación de los tres modelos básicos.

El modelo físico de Melzak consiste en agujeros {X, Y, Z, etc.} en el suelo junto con un suministro ilimitado de guijarros en un agujero especial S (¿sumidero, suministro o ambos? Melzak no lo especifica).

"La máquina Q consta de un número indefinidamente grande de ubicaciones : S, A1, A2, ..., un suministro indefinidamente grande de contadores distribuidos entre estas ubicaciones, un programa y un operador cuyo único propósito es ejecutar las instrucciones. Inicialmente, todas las ubicaciones, excepto un número finito de ellas, están vacías, y cada una de las restantes contiene un número finito de contadores " (p. 283, negrita añadida).

La instrucción es una única " operación ternaria " que él llama "XYZ":

"XYZ" denota la operación de

1. Cuenta el número de guijarros en el agujero Y ,
2. volver a colocarlos en Y ,
3. intentar eliminar este mismo número del agujero X. SI esto no es posible porque vaciará el agujero X ENTONCES no hacer nada y saltar a la instrucción #I; DE LO CONTRARIO,
4. (iv) quitar la cantidad Y de X y (v) transferirlas a, es decir, agregarlas a , la cantidad en el agujero Z.

De todas las operaciones posibles, algunas no están permitidas, como se muestra en la tabla a continuación:

Algunas observaciones sobre el modelo de Melzak :

Modelo original de "ábaco" de Lambek (1962):

Lambek cita el artículo de Melzak. Descompone la operación de tres parámetros de Melzak (en realidad cuatro si contamos las direcciones de las instrucciones) en un incremento de dos parámetros, "X+", y un decremento de tres parámetros, "X-". También proporciona una definición, tanto informal como formal , de "un programa". Esta forma es prácticamente idéntica al modelo de Minsky (1961) y ha sido adoptada por Boolos, Burgess y Jeffrey (2007 , pág. 45), en Abacus Computability . 

Modelo de ábaco de Boolos, Burgess y Jeffrey : ^{[ 5 ]}

En las distintas ediciones que comienzan con 1970, los autores utilizan el modelo de Lambek (1961) de un "ábaco infinito". Esta serie de artículos de Wikipedia utiliza su simbolismo, por ejemplo, "[ r ] +1 → r" "el contenido del registro identificado como número 'r', más 1, reemplaza el contenido de [se coloca en] el registro número 'r'".

Utilizan el nombre "ábaco" de Lambek, pero siguen el modelo de Melzak de "guijarros en agujeros", modificado por ellos a un modelo de "piedras en cajas". Al igual que el modelo original de ábaco de Lambek, su modelo conserva el uso de Minsky (1961) de instrucciones no secuenciales ; a diferencia de la ejecución de instrucciones secuenciales predeterminadas "convencionales" de las computadoras, la siguiente instrucción I _a está contenida dentro de la instrucción. 

Sin embargo, observe que BB y BBJ no utilizan una variable "X" en los mnemónicos con un parámetro de especificación (como se muestra en la versión de Lambek) --es decir, "X+" y "X-" - sino que los mnemónicos de la instrucción especifican los registros mismos, por ejemplo, "2+" o "3-": 

Shepherdson y Sturgis (1963) hacen referencia a Minsky (1961) tal como les apareció en forma de informe del Laboratorio Lincoln del MIT :

En la Sección 10 mostramos que los teoremas (incluidos los resultados de Minsky [21, su referencia]) sobre el cálculo de funciones recursivas parciales mediante una o dos cintas se pueden obtener de manera bastante sencilla a partir de una de nuestras formas intermedias.

Su modelo está fuertemente influenciado por el modelo y el espíritu de Hao Wang (1957) ^{[ 6 ]} y su máquina Wang B (véase también Máquina post-Turing ). Lo resumen diciendo:

...hemos intentado llevar un paso más allá el "acercamiento" entre los aspectos prácticos y teóricos de la computación sugerido e iniciado por Wang.

Máquina de Registros Ilimitados (URM) : ^{[ 7 ]} Esta, su "máquina más flexible... consiste en una secuencia numerable de registros numerados del 1 al 3, cada uno de los cuales puede almacenar cualquier número natural ... Sin embargo, cada programa particular involucra solo un número finito de estos registros" (p.  219). En otras palabras, el número de registros es potencialmente infinito, y el "tamaño" de cada registro es infinito.

Ofrecen el siguiente conjunto de instrucciones y las siguientes "Notas": ^{[ 1 ]}

Notas.

1. Este conjunto de instrucciones se elige por su facilidad de programación para el cálculo de funciones recursivas parciales, más que por su economía; en la Sección 4 se demuestra que este conjunto es equivalente a un conjunto más pequeño.
2. Hay infinitas instrucciones en esta lista ya que m, n [contenido de r _j , etc.] abarcan todos los enteros positivos.
3. En las instrucciones a, b, c, d se supone que el contenido de todos los registros excepto n debe permanecer sin cambios; en las instrucciones e, f, el contenido de todos los registros permanece sin cambios (pág.  219).

De hecho, muestran cómo reducir aún más este conjunto, al siguiente (para un número infinito de registros, cada uno de tamaño infinito):

Máquina de Registro Limitado (LRM ): Aquí restringen la máquina a un número finito de registros N, pero también permiten que se "incorporen" o se eliminen más registros si están vacíos (véase pág.  228). Demuestran que la instrucción para eliminar un registro no requiere necesariamente que este esté vacío.

Máquina de registro único (SRM) : Aquí implementan el sistema de etiquetas de Emil Post , permitiendo escribir solo hasta el final de la cadena y borrar desde el principio. Esto se muestra en su Figura 1 como una cinta con un cabezal de lectura a la izquierda y un cabezal de escritura a la derecha, y solo puede mover la cinta hacia la derecha. "A" es su "palabra" (pág.  229):

a. P(i); agregar ai al final de A

b. D; elimine la primera letra de A

f'. Ji[E1] ;Si A comienza con ai, salta a la salida 1.

También proporcionan un modelo como "una pila de cartas" con los símbolos { 0, 1 } (pág.  232 y Apéndice C, pág.  248):

1. agregar tarjeta en la parte superior impresa 1
2. agregar tarjeta en la parte superior impresa 0
3. Retire la tarjeta inferior; si se imprime 1, salte a la instrucción m, de lo contrario, a la siguiente instrucción.

En última instancia, en el Problema 11.7-1, Minsky observa que se pueden formar muchas bases de computación a partir de una pequeña colección:

"Muchas otras combinaciones de tipos de operaciones [ 0 ], [ ' ], [ - ], [ O- ], [ → ] y [ RPT ] forman bases universales. Encuentra algunas de estas bases. ¿Qué combinaciones de tres operaciones no son bases universales? Inventa otras operaciones..." ^{[ 10 ]}

A continuación se presentan las definiciones de las diversas instrucciones que trata:

Minsky (1967) comienza con un modelo que consta de las tres operaciones más HALT:

{ [ 0 ], [ ' ], [ - ], [ H ] }

Observa que podemos prescindir de [ 0 ] si permitimos un registro específico, por ejemplo, w ya "vacío". ^{[ 11 ]} Más adelante comprime los tres { [ 0 ], [ ' ], [ - ] } en dos { [ ' ], [ - ] }. ^{[ 12 ]}

Pero admite que el modelo es más fácil si agrega algunas [pseudo]-instrucciones [ O- ] (combinando [ 0 ] y [ - ]) y "go(n)". Construye "go(n)" a partir del registro w preestablecido a 0, de modo que [O-] ( w , (n)) es un salto incondicional.

En su sección 11.5 "La equivalencia de las máquinas de programas con funciones recursivas generales" introduce dos nuevas subrutinas:

f. [ → ]

j. [ ≠ ]

Saltar a menos que sean iguales": SI [ r _j ] ≠ [ r _k ] ENTONCES saltar a la instrucción z SI NO la siguiente instrucción

A continuación, muestra cómo reemplazar el conjunto "sucesor-predecesor" { [ 0 ], [ ' ], [ - ] } con el conjunto "sucesor-igualdad" { [ 0 ], [ ' ], [ ≠ ] }. Luego define su "REPETIR" [RPT] y muestra que podemos definir cualquier función recursiva primitiva mediante el conjunto "sucesor-repetir" { [ 0 ], [ ' ], [RPT] } (donde el rango de [ RPT ] no puede incluirse a sí mismo. Si lo hace, obtenemos lo que se denomina el operador mu (véase también funciones recursivas mu ) (pág.  213)):

Cualquier función recursiva general puede ser calculada por una computadora de programa usando solo las operaciones [ 0 ], [ ' ], [ RPT ] si permitimos que una operación RPT se encuentre dentro de su propio rango... [sin embargo], en general, una operación RPT no podría ser una instrucción en la parte de estados finitos de la máquina... [si lo fuera], esto podría agotar cualquier cantidad particular de almacenamiento permitida en la parte finita de la máquina. Las operaciones RPT requieren registros infinitos propios, en general... etc." (p. 214)

Schönhage (1980) ^{[ 13 ]} desarrolló su modelo computacional en el contexto de un "nuevo" modelo que denominó modelo de modificación de máquina de almacenamiento (SMM), su variedad de máquina de punteros . Su desarrollo describió un modelo de RAM ( máquina de acceso aleatorio ) con un conjunto de instrucciones notable que no requería ningún operando, excepto, quizás, el "salto condicional" (e incluso eso podría lograrse sin un operando):

"...la versión RAM0 merece especial atención por su extrema simplicidad; su conjunto de instrucciones consta de tan solo unos pocos códigos de una letra, sin ningún direccionamiento (explícito)" (p. 494)

La forma en que Schönhage lo hizo es interesante. Él (i) atomiza el registro convencional "dirección:dato" en sus dos partes: "dirección" y "dato", y (ii) genera la "dirección" en un registro específico n al que tendrían acceso las instrucciones de la máquina de estados finitos (es decir, el " código máquina "), y (iii) proporciona un registro "acumulador" z donde se realizarán todas las operaciones aritméticas.

Su modelo RAM0 particular solo tiene dos "operaciones aritméticas" : "Z" para "poner a cero el contenido del registro z " y "A" para "sumar uno al contenido del registro z ". El único acceso al registro de dirección n es mediante una instrucción de copia de A a N llamada "establecer dirección n ". Para almacenar un "dato" en el acumulador z en un registro determinado, la máquina utiliza el contenido de n para especificar la dirección del registro y el registro z para proporcionar el dato que se enviará al registro. 

Peculiaridades: Una primera peculiaridad de la RAM0 de Schönhage es cómo "carga" algo en el registro z : el registro z primero proporciona la dirección del registro y luego, en segundo lugar, recibe el dato del registro , una forma de "carga" indirecta. La segunda peculiaridad es la especificación de la operación COMPARE. Esta es un "salto si el registro acumulador z = cero " (no, por ejemplo, "compara el contenido de z con el contenido del registro al que apunta n "). Aparentemente, si la prueba falla, la máquina omite la siguiente instrucción, que siempre debe ser de la forma "goto λ", donde "λ" es la dirección de salto. La instrucción " comparar el contenido de z con cero " es diferente del modelo sucesor de la RAM1 de Schönhage (o de cualquier otro modelo sucesor conocido) con la instrucción más convencional "comparar el contenido del registro z con el contenido del registro a para ver si son iguales".  

Principalmente a modo de referencia ( este es un modelo de RAM, no un modelo de máquina contadora ), a continuación se muestra el conjunto de instrucciones RAM0 de Schönhage:  

Nuevamente, el conjunto de instrucciones anterior es para una máquina de acceso aleatorio , una RAM , una máquina de contador con direccionamiento indirecto; la instrucción "N" permite el almacenamiento indirecto del acumulador, y la instrucción "L" permite la carga indirecta del acumulador. 

Aunque peculiar, el modelo de Schönhage muestra cómo el conjunto de instrucciones "de registro a registro" o "de lectura, modificación y escritura" de la máquina contadora convencional se puede atomizar a su forma más simple de 0 parámetros.