Modelo de contra-máquina - Counter-machine model

Aunque algunos autores utilizan el nombre de " registrar máquinas " como sinónimo de " máquina de venta libre ", este artículo le dará detalles y ejemplos de solamente de las especies más primitivas - la "máquina de venta libre" - del género "registro de la máquina."

Dentro de la especie "máquina contador" hay una serie de variedades: los modelos de Hermes (1954), Kaphengst (1957), Ershov (1958), Péter (1958), Minsky (1961) y Minsky (1967), Melzak (1961). ), Lambek (1961), Shepherdson y Sturgis (1963) y Schönhage (1980). Estos modelos se describirán con más detalle a continuación.

Los modelos con más detalle

1954: modelo de Hermes

Shepherdson y Sturgis 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 se podía programar una computadora idealizada para duplicar el comportamiento de cualquier máquina de Turing "(Shepherdson y Sturgis, p. 219).

Shepherdson y Sturgis observan que:

"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 de ellos capaz de almacenar palabras arbitrariamente largas" (Shepherdson y Sturgis, p. .219)

Las únicas dos instrucciones aritméticas son

1. Operación sucesora
2. Probando dos números para la igualdad

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 "pedidos".

La máquina contiene "un molino" (acumulador). Kaphengst designa su molino / acumulador con el símbolo "infinito" pero usaremos "A" en la siguiente descripción. También contiene un "registro de orden" ("orden" como en "instrucción", no como en "secuencia"). (Este uso proviene de la descripción del informe de Burks-Goldstine-von Neumann (1946) de "... un instrumento de cómputo electrónico".) El registro de orden / instrucción es el registro "0". Y, aunque no está claro a partir de la exposición de Sheperdson y Sturgis, el modelo contiene un "registro de extensión" designado por Kaphengst como "infinity-prime"; usaremos "E".

Las instrucciones se almacenan en los registros:

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

Por tanto, este modelo es en realidad una máquina de acceso aleatorio . A continuación, "[r]" indica "contenido del" registro r, etc.

		Acción:	Descripción
D1:	C (r, A)	[r] → A, [r] → r	Copie el contenido del registro r al acumulador A
D2:	Coche)	[A] → r, [A] → A	Copie el contenido del acumulador A para registrar r
C1:	O (A)	0 → A	Acumulador A cero (claro)
A1:	PENSILVANIA)	[A] + 1 → A	Incrementar (agregar 1 a) el contenido del acumulador A
F1:	J (A) [E1]	SI [A] = 0 ENTONCES salta a "Salida 1"	Saltar si el contenido del acumulador A = 0
G1:	En un)	SI [A] = [r] ENTONCES 0 → <A> ELSE 1 → A	Limpiar el contenido de A si el contenido de A = contenido de r, de lo contrario "establecer" A = 1
G2:	O '(A)	1 → A	"Establecer" contenido de A = 1

Shepherdson y Sturgis eliminan el molino / acumulador A y reducen las instrucciones de Kaphengst a "copiar" de registro a registro, "incrementar" la operación aritmética y "comparar registro a registro". Observe que no hay decremento . Este modelo, casi literalmente, se encuentra en Minsky (1967); vea más en la sección a continuación.

		Acción:	Descripción:
a:	PENSILVANIA)	[A] + 1 → A	Incrementar (agregar 1 a) el contenido del acumulador A
D.	C (r j , r k )	[r j ] → r k , [r j ] → r j	Copiar el contenido del registro r j al registro r k
F:	J (r) [E1]	SI [r] = 0 ENTONCES salta a "Salida 1" ELSE siguiente instrucción	Saltar si el contenido del registro r = 0
C:	E (r j , r k )	SI [r j ] = [r k ] ENTONCES 0 → E ELSE 1 → E	Limpiar el contenido del registro E si el contenido de r j = contenido de r k , de lo contrario "establecer" E = 1

1958: la clase de algoritmos de operador de Ershov

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:

		Acción:	Descripción:
D.	C (r j , r k )	[r j ] → r k , [r j ] → r j	Copiar el contenido del registro r j al registro r k
D'.	C '(r j , r k )	[r j ] +1 → r k , [r j ] → r j	Copiar el contenido incrementado del registro r j al registro r k
mi.	J [E1]	Ir a "Salida 1"	Salto incondicional a "Salida n. ° 1"
F*:	J (r j , r k ) [E1, E2]	SI [r j ] ≤ [r k ] ENTONCES salta a "Salida 1" ELSE salta a "Salida 2"	Salte para salir de E1 si el contenido del registro r j es menor o igual que el contenido de r k , de lo contrario salte a E = 2

1958: el "trato" de Péter

Shepherdson y Sturgis (1963) observan que el "tratamiento" de Péter (no son demasiado específicos aquí) 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 probar su computabilidad mediante máquinas de Turing es necesario un análisis más detallado de la operación de copia siguiendo las líneas que hemos tomado anteriormente". (Shepherdson y Sturgis (1963) pág.246)

		Acción:	Descripción:
C:	En)	0 → [n]	Registro cero (claro) n
D.	C (m, n)	[m] → n, [m] → [m]	Copiar el contenido del registro m al registro n
D'.	C '(m, n)	[m] + 1 → [n], [m] → [m]	Copiar el contenido incrementado del registro m al registro n
mi.	J (m, n) [E1, E2]	SI [m] = [n] saltar a E1 ELSE saltar a E2	Salta condicional a E1 si el contenido de m es igual al contenido de n; de lo contrario, salta a E2.

1961: el modelo de Minsky de una función recursiva parcial reducido a un "programa" de sólo dos instrucciones

En su investigación sobre los problemas de Emil mensaje (el sistema de etiquetas ) y Hilbert 10a problema 's ( los problemas de Hilbert , la ecuación Diophantine ) llevado Minsky a la siguiente definición:

"una base interesante para la teoría de funciones recursivas que involucran programas de sólo las operaciones aritméticas más simples" (Minsky (1961) p. 437).

Su "Teorema Ia" afirma que cualquier función recursiva parcial está representada por "un programa que opera en dos enteros S1 y S2 usando las instrucciones Ij de las formas (cf. Minsky (1961) p. 449):

		Acción:	Descripción:
un.	AÑADIR (r, I j1 )	[r] + 1 → r; vaya a la instrucción I j1 .	Incremente (agregue 1 a) el contenido del registro r y vaya a la instrucción I j1 .
B.	SUB (r, yo j1 , yo j2 )	Si [r] ≤ 0 ENTONCES vaya a instr. I j2 ELSE [r] -1 → r y voy a instr. Yo j1	SI el contenido del registro r es igual a cero ENTONCES salte a la instrucción I j2 ; ELSE decrementa (resta 1 de) el contenido del registro r y salta a instr. Yo j1 .

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

"... representa cualquier función recursiva parcial por un programa que opera en un entero S [contenido en un solo registro r1] usando las instrucciones I _j de las formas":

		Acción:	Descripción:
un.	MULT (K j , I j1 )	[r1] * K j → r1; vaya a la instrucción I j1 .	Multiplica el contenido del registro r1 por la constante K j
B.	DIV (K j , I j1 , I j2 )	[r1] / Kj = 0, luego vaya a la instrucción I j2; de lo contrario, vaya a I j1 .	Si la división del contenido del registro 1 por la constante K j no tiene resto, entonces instr. I j1 else instr. Yo j2

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

1961: modelo de Melzak: una sola instrucción ternaria con suma y resta propia

"Nuestro objetivo es describir un dispositivo primitivo, que se llamará una máquina Q, que llega a la computabilidad efectiva a través de 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ág.281)

Si usamos el contexto de su modelo, "llevar la cuenta" significa "sumar por incrementos sucesivos" (arrojar un guijarro) o "restar por 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 son agujeros {X, Y, Z, etc.} en el suelo junto con un suministro ilimitado de guijarros en un agujero especial S (¿Sumidero o Suministro o ambos? Melzak no lo dice).

"La máquina Q consta de un número indefinidamente grande de ubicaciones : S, A1, A2, ..., una oferta indefinidamente grande de contadores distribuidos entre estas ubicaciones, un programa y un operador cuyo único propósito es llevar a cabo las instrucciones. . Inicialmente, todos menos un número finito de entre las ubicaciones ... están vacíos y cada uno de los restantes contiene un número finito de contadores "(p. 283, negrita agregada)

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

"XYZ" denota el funcionamiento de

1. Cuente el número de guijarros en el hoyo Y ,
2. ponlos de nuevo en Y ,
3. intente quitar este mismo número de agujero X . SI esto no es posible porque vaciará el agujero X ENTONCES no haga nada y salte a la instrucción #I; DEMÁS,
4. quitar el Y-Cantidad de X y (iv) transferirlos a, es decir, añadir a, la cantidad en el agujero Z .

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

Permitido	Instrucción	Agujero "X"	Agujero "Y"	Agujero "Z"	Significado de la instrucción
NO	XXX
	XXY	([X] - [X]) = 0 → X	[Y] + [X] → Y	[Z] → Z	Todos los guijarros de X tomados de X y agregados a Y
	XXS	([X] - [X]) = 0 → X	[Y] → Y	[Z] → Z	Todos los guijarros de X tomados de X y puestos en el sumidero / fuente S
NO	XYX
	XYY	[X] - [Y] → X	[Y] + [Y] → Y	[Z] → Z	Recuento de guijarros de Y tomados de X y colocados en Y, duplicando el recuento de Y
	XYS
NO	XSX
NO	XSY
NO	XSS
	XYZ	[X] - [Y] → X	[Y] → Y	[Z] + [Y] → Z	Recuento de guijarros de Y tomados de X y sumados a Z,
	SYY	[X] → X	[Y] + [Y] → Y	[Z] → Z	Recuento de guijarros de Y tomados de S y sumados a Y, duplicando el recuento de Y
	SYZ	[X] → X	[Y] → Y	[Z] + [Y] → [Z]	Recuento de guijarros de Y tomados de S y agregados a Z

Algunas observaciones sobre el modelo de Melzak :

1961: modelo de "ábaco" de Lambek: atomización del modelo de Melzak a X +, X- con prueba

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

Lambek hace referencia al artículo de Melzak. Atomiza la operación de 3 parámetros de Melzak (en realidad 4 si contamos las direcciones de instrucción) en un incremento de 2 parámetros "X +" y un decremento de 3 parámetros "X-". También proporciona una definición formal e informal de "un programa". Esta forma es prácticamente idéntica al modelo de Minsky (1961) y ha sido adoptada por Boolos-Burgess-Jeffrey (2002).

		Acción:	Descripción:
un.	X + (r, yo a )	[r] + 1 → r; ir a la instrucción I a .	Incrementar (agregar 1 a) el contenido del registro r
B.	X- (r, yo a , yo b )	Si [r] ≤ 0, vaya a instr.I b else [r] -1 → r y vaya a instr. Yo un	Primero pruebe cero, luego disminuya (reste 1 de) el contenido del registro r

Modelo de ábaco de Boolos-Burgess (1970, etc.), Boolos-Burgess-Jeffrey (2002) :

Las diversas ediciones a partir de 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 el número 'r', más 1, reemplaza el contenido de [se coloca en] el número de registro 'r'" .

Usan el nombre de Lambek "ábaco" pero siguen el modelo de guijarros en los agujeros de Melzak, modificado por ellos a un modelo de "piedras en cajas". Al igual que el modelo de ábaco original de Lambek, su modelo retiene el uso de instrucciones no secuenciales de Minsky (1961); a diferencia de la ejecución de instrucción secuencial predeterminada "convencional" similar a una computadora, la siguiente instrucción I _a está contenida dentro de la instrucción.

Observe, sin embargo, que BB y BBJ no usan 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 instrucción especifican el se registra a sí mismo, por ejemplo, "2+" o "3-":

		Acción:	Descripción:
a1.	1+ (yo a )	[r1] + 1 → r1 luego vaya a la instrucción I a .	Incrementar (agregar 1 a) el contenido del registro # 1
b1.	1- (yo a , yo b )	Si [r1] ≤ 0 ENTONCES vaya a I b si no [r1] -1 → r1 y vaya a I a .	Salte a la instrucción I b si el contenido del registro r1 es cero ELSE disminuya (reste 1 de) el contenido del registro # 1

1963: el modelo de Shepherdson y Sturgis

En la página 218, Shepherdson y Sturgis hacen referencia a Minsky (1961) tal como les apareció en la forma de un 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 pueden obtenerse con bastante facilidad a partir de una de nuestras formas intermedias (p. 218).

Su modelo está fuertemente influenciado por el modelo y el espíritu de Hao Wang (1957) y su máquina Wang B (ver también Máquina Post-Turing ). Ellos "resumen diciendo":

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

Máquina de registro ilimitado URM : Esta, su "máquina más flexible ... consiste en una secuencia numerable de registros numerados 1, 2, 3, ..., cada uno de los cuales puede almacenar cualquier número natural ... Cada programa en particular, sin embargo implica sólo 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 (p. 219) y las siguientes "Notas":

	Modelo URM:	Acción:	Descripción:
un.	P (n)	[r] + 1 → r	Incrementar (agregar 1 a) el contenido del registro r
B.	D (n)	[r] - 1 → r	Disminuir (restar 1 de) el contenido del registro r
C:	En)	0 → r	Registro cero (borrar) r
D.	C (m, n)	[r j ] → r k , [r j ] → r j ,	Copiar el contenido del registro r j al registro r k
mi.	J [E1]	Ir a "Salida 1"	Salto incondicional a "Salida n. ° 1"
F:	J (r) [E1]	SI [r j ] = 0 ENTONCES salta a "Salida 1" ELSE siguiente instrucción	SI el contenido del registro r = 0, luego salte a la instrucción "Exit 1"; de lo contrario, a continuación instrucción

Notas.

1. Este conjunto de instrucciones se elige para facilitar la programación del cálculo de funciones recursivas parciales en lugar de la economía; se muestra en la Sección 4 que este conjunto es equivalente a un conjunto más pequeño.
2. Hay infinitas instrucciones en esta lista ya que m, n [contenidos 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 no se modifica; en las instrucciones e, f, el contenido de todos los registros no se modifica (p. 219).

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

	URM reducido:	Acción:	Descripción:
a1.	P (r)	[r] + 1 → r	Incrementar (agregar 1 a) el contenido del registro r
b1.	D (n)	[r] - 1 → r	Disminuir (restar 1 de) el contenido del registro r
~ f1:	J (r) [E1]	SI [r] ≠ 0 ENTONCES salta a "Salida 1"	Si el contenido del registro m ≠ 0 ENTONCES salte a la instrucción "Salir 1" ELSE continúe

Máquina de registros limitados LRM : aquí restringen la máquina a un número finito de registros N, pero también permiten "traer" o eliminar más registros si están vacíos (cf. p. 228). Muestran que la instrucción de eliminación de registro no necesita requerir un registro vacío.

SRM de máquina de registro único : aquí están implementando el sistema de etiquetas de Emil Post y, por lo tanto, solo permiten escribir 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. 229):

un. P (i); agregue ai al final de A

B. D; eliminar 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. 232 y Apéndice C, p. 248):

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

1967: "Base universal simple para una computadora de programa" de Minsky

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

"Muchas otras combinaciones de tipos de operaciones [0], ['], [-], [O-], [→] y [RPT] forman una base universal. Encuentre algunas de estas bases. ¿Qué combinaciones de tres operaciones no son una base universal? ? Inventa algunas otras operaciones ... "(p. 214)

Las siguientes son definiciones de las diversas instrucciones que trata:

		Acción:	Descripción:
un.	[0]	0 → r	Registro cero (borrar) r
B.	[']	[r] + 1 → r	Incrementar (agregar 1 a) el contenido del registro r (apóstrofe 'significa "sucesor")
C.	[-]	SI [r] = 0 ENTONCES saltar a la instrucción z ELSE siguiente instrucción	Pruebe el registro r y salte a la instrucción z si el contenido es cero; si no es así, decrementar (restar 1 de) el contenido del registro r
D.	[O-]	Si [r] ≠ 0 THEN [r] -1 → r ELSE siguiente instrucción	SI el contenido del registro r no es cero, disminuya el contenido del registro r y salte a la instrucción z, de lo contrario, si es 0, entonces la siguiente instrucción
mi.	[→]	[r j ] → r k , [r j ] → r j	Copiar el contenido del registro r j al registro r k
F.	[RPT]	RPT a: [m, n]. La repetición no puede funcionar dentro de su propio rango.	Continúe hasta que el contenido del registro [r] = 0: Repita las instrucciones de la m a la n. Cuando [r] = 0, vaya a la siguiente instrucción.
gramo.	[H]	DETENER
h.	ir a (z)	Ir a la instrucción z	Salto incondicional a la instrucción z
I.	[≠]	Si [r j ] ≠ [r k ] ENTONCES salta a la instrucción zth ELSE siguiente instrucción	Salto condicional: si el contenido del registro r j no es igual al contenido del registro r k ENTONCES salta a la instrucción z ELSE siguiente instrucción
j.	[RPT] *	RPT a: [m, n]. Repeat puede operar dentro de su propio rango.	* Nota: RPT debe estar en un registro infinito

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" (Minsky (1967) p. 206). Más tarde (páginas 255 y siguientes) comprime los tres {[0], ['], [-]}, en dos {['], [-]}.

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

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

F. [→]

j. [≠]

Saltar a menos que sea igual ": SI [r _j ] ≠ [r _k ] ENTONCES salta a la instrucción zth ELSE siguiente instrucción

Él procede a mostrar cómo reemplazar el conjunto "sucesor-predecesor" {[0], ['], [-]} con el conjunto "sucesor-igualdad" {[0], ['], [≠]}. Y luego define su "REPEAT" [RPT] y muestra que podemos definir cualquier función recursiva primitiva por el "sucesor-repeat" conjunto {[0], ['], [RPT]} (donde el rango de la [RPT ] no puede incluirse a sí mismo. Si lo hace, obtenemos lo que se llama el operador mu (ver también funciones recursivas mu ) (p. 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 en su propio rango ... [sin embargo] en general una operación RPT no podría ser una instrucción en la parte de estado finito de la máquina ... [si lo fuera] esto podría agotar cualquier cantidad particular de almacenamiento permitido en la parte finita de la máquina. Las operaciones RPT requieren infinitos registros propios, en general ... etc. "(p. 214)

1980: modelo RAM0 de 0 parámetros de Schönhage

Schönhage (1980) desarrolló su modelo computacional en el contexto de un modelo "nuevo" que llamó modelo de modificación de la máquina de almacenamiento (SMM), su variedad de máquina puntero . Su desarrollo describió un modelo de RAM ( máquina de acceso aleatorio ) con un conjunto de instrucciones notable que no requiere operandos en absoluto, excepto, quizás, el "salto condicional" (e incluso eso podría lograrse sin un operando):

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

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

En su modelo RAM0 particular tiene sólo dos "operaciones aritméticas": "Z" para "establecer el contenido del registro z en cero", y "A" para "agregar uno al contenido del registro z ". El único acceso al registro de direcciones n es a través de 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 dado, la máquina usa el contenido de n para especificar la dirección del registro y el registro z para suministrar el dato que se enviará al registro.

Peculiaridades: Una primera peculiaridad de Schönhage RAM0 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. Este es un "salto si el registro acumulador z = cero (no, por ejemplo," comparar el contenido de z con el contenido del registro apuntado por n ). Aparentemente, si la prueba falla, la máquina salta la siguiente instrucción que siempre debe tener la forma de "goto λ" donde "λ" es la dirección de salto. La instrucción "comparar el contenido de z con cero " es diferente al modelo sucesor-RAM1 de Schonhage (o cualquier otro modelo sucesor conocido) con el más convencional "comparar el contenido del registro z con el contenido del registro a para la igualdad".

Principalmente como referencia, este es un modelo de RAM, no un modelo de máquina contraria, el siguiente es el conjunto de instrucciones de Schönhage RAM0:

	Instrucción	Acción:	Descripción:
1	Z	0 → z	Borrar acumulador-registro z
2	A	[z] + 1 → z	Incrementar el contenido del registro acumulador z
3	norte	[z] → n, [z] → z	"Establecer dirección n": copia el contenido del acumulador z en el registro de direcciones n
4	L	[[z]] → z	Copie indirectamente en el acumulador z el contenido del registro apuntado por el acumulador z
5	S	[z] → [n]	Almacene indirectamente el contenido del acumulador z en el registro al que apunta el contenido del registro de direcciones n
6	C	Si [z] = 0 omita la siguiente instrucción (que debe ser una instrucción goto I λ )	Si el contenido del acumulador z = 0 ENTONCES omita la siguiente instrucción; de lo contrario, continúe
7	ir a I λ	Instrucción goto (saltar a) incondicional I λ	Instrucción goto (saltar a) incondicional I λ

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.

Si bien es peculiar, el modelo de Schönhage muestra cómo el conjunto de instrucciones de "registro a registro" o "lectura-modificación-escritura" de la máquina contador convencional se puede atomizar a su forma de parámetro 0 más simple.

Referencias

• George Boolos , John P. Burgess , Richard Jeffrey (2002), Computabilidad y lógica: Cuarta edición , Cambridge University Press, Cambridge, Inglaterra. El texto original de Boolos-Jeffrey ha sido revisado extensamente por Burgess: más avanzado que un libro de texto introductorio. El modelo de "máquina de á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 (todavía en la forma original de 4 tuplas de Boolos) y la recursividad los otros dos.
• Fischer, Patrick C .; Meyer, AR ; Rosenberg, Arnold L. (1968), "Máquinas de contador y lenguajes de contador", Teoría de sistemas matemáticos , 2 : 265-283, doi : 10.1007 / bf01694011 , MR  0235932. Desarrolla teoremas de jerarquía de tiempo y jerarquía de espacio para máquinas contadoras, análogas a las jerarquías de máquinas de Turing.
• 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 enlazadas".
• Joachim Lambek (1961, recibido el 15 de junio de 1961), Cómo programar un ábaco infinito , Boletín matemático, vol. 4, no. 3. Septiembre de 1961 páginas 295–302. 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 .
• ZA Melzak (1961, recibido el 15 de mayo de 1961), Un enfoque aritmético informal a la computabilidad y la computación , Canadian Mathematical Bulletin , vol. 4, no. 3. Septiembre de 1961 páginas 279-293. Melzak no ofrece referencias, pero reconoce "el beneficio de las conversaciones con los doctores R. Hamming, D. McIlroy y V. Vyssots de los Bell Telephone Laborators y con el Dr. H. Wang de la Universidad de Oxford".
• Marvin Minsky (1961, recibido el 15 de agosto de 1960). "Inestabilidad recursiva del problema de Post de 'etiqueta' y otros temas en la teoría de las máquinas de Turing". Annals of Mathematics . Annals of Mathematics. 74 (3): 437–455. doi : 10.2307 / 1970290 . JSTOR  1970290 . Verifique los valores de fecha en: |date=( ayuda )
• Marvin Minsky (1967). Computación: máquinas finitas e infinitas (1ª ed.). Englewood Cliffs, Nueva Jersey: Prentice-Hall, Inc.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.
• John C. Shepherdson y HE Sturgis (1961) recibieron en diciembre de 1961 Computability of Recursive Functions , Journal of the Association of Computing Machinery (JACM) 10: 217-255, 1963. Un artículo de referencia extremadamente valioso. En su Apéndice A, los autores citan otros 4 con referencia a "Mínimo de instrucciones utilizadas en 4.1: Comparación con sistemas similares".
  • Kaphengst, Heinz, Eine Abstrakte programmgesteuerte Rechenmaschine ' , Zeitschrift für Mathische Logik und Grundlagen der Mathematik: 5 (1959), 366-379.
  • Ershov, AP Sobre algoritmos de operador , (ruso) Dok. Akad. Nauk 122 (1958), 967-970. Traducción al inglés, Automat. Express 1 (1959), 20-23.
  • Péter, Rózsa Graphschemata und rekursive Funktionen , Dialectica 12 (1958), 373.
  • Hermes, Hans Die Universalität programmgesteuerter Rechenmaschinen. Math.-Phys. Semesterberichte (Göttingen) 4 (1954), 42–53.
• A. 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 el "sucesor RAM" (Random Access Machine), etc.
• Rich Schroeppel , mayo de 1972, "Una máquina de dos contadores no puede calcular 2 ^N ", Instituto de Tecnología de Massachusetts, Laboratorio de IA, Nota de inteligencia artificial # 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".
• Peter van Emde Boas , Machine Models and Simulations págs. 3-66, que aparece en:

Jan van Leeuwen , ed. "Handbook of Theoretical Computer Science. Volumen A: Algoritmos y complejidad , The MIT PRESS / Elsevier, 1990. ISBN  0-444-88071-2 (volumen A). QA 76.H279 1990.

El tratamiento de van Emde Boas de los SMM aparece en las págs. 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 eficaz.

• 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 Informática) 4; 63–92. Presentado en la reunión de la Asociación, 23-25 ​​de junio de 1954.