Máquina contadora

Máquina abstracta utilizada en la lógica formal y la informática teórica.

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

Las máquinas de contador con tres contadores pueden calcular cualquier función recursiva parcial de una sola variable. Las máquinas de contador con dos contadores son Turing completas : pueden simular cualquier máquina de Turing codificada apropiadamente, pero hay algunas funciones simples que no pueden calcular. Las máquinas de contador con un solo contador pueden reconocer un superconjunto adecuado de los lenguajes regulares y un subconjunto de los lenguajes deterministas libres de contexto . ^[1]

Características básicas

Para un modelo de máquina contadora dado, el conjunto de instrucciones es minúsculo: desde una hasta seis o siete instrucciones. La mayoría de los modelos contienen unas pocas operaciones aritméticas y al menos una operación condicional (si la condición es verdadera, entonces se salta). Tres modelos básicos , cada uno de los cuales utiliza tres instrucciones, se extraen de la siguiente colección. (Las abreviaturas son arbitrarias.)

• CLR (r): CLeaR registro r . (Establecer r en cero).
• INC (r): INCrema el contenido del registro r .
• DEC (r): decrementa el contenido del registro r .
• CPY (r _j , r _k ): Copia el contenido del registro r _j al registro r _k dejando intacto el contenido de r _j .
• JZ (r, z): SI el registro r contiene cero ENTONCES Salta a la instrucción z DE LO CONTRARIO continúa en secuencia.
• JE (r _j , r _k , z): SI el contenido del registro r _j es igual al contenido del registro r _k ENTONCES Salta a la instrucción z DE LO CONTRARIO continúa en secuencia.

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

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

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

Los tres modelos básicos de máquinas de contador tienen la misma potencia computacional, ya que las instrucciones de un modelo pueden derivarse de las de otro. Todos son equivalentes a la potencia computacional de las máquinas de Turing . Debido a su estilo de procesamiento unario, las máquinas de contador suelen ser exponencialmente más lentas que las máquinas de Turing comparables.

Nombres alternativos, modelos alternativos

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

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

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

• Máquina de Minsky , porque Marvin Minsky (1961) formalizó el modelo. Generalmente utiliza el conjunto de instrucciones (1), pero la ejecución de instrucciones no es secuencial por defecto, por lo que el parámetro adicional 'z' parece especificar la siguiente instrucción después de INC y como alternativa en JZDEC:

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

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

  { INC ( r ), DEC ( r ), JZ ( r, z _verdadero )}

• Máquina de ábaco , nombre que Lambek (1961) dio a su simplificación del modelo de Melzak (1961), y que Boolos–Burgess–Jeffrey (2002) denomina. Utiliza el conjunto de instrucciones (1) pero con un parámetro adicional z para especificar la siguiente instrucción a la manera del modelo de Minsky (1961);

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

• Máquina Lambek , nombre alternativo que Boolos–Burgess–Jeffrey (2002) le dio a la máquina ábaco. Utiliza un conjunto de instrucciones (1-reducido) con un parámetro adicional para especificar la siguiente instrucción:

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

• Máquina sucesora , porque utiliza la 'operación sucesora' de los axiomas de Peano y se parece mucho a ellos. Se utiliza como base para el modelo de RAM sucesora . Utiliza el conjunto de instrucciones (2) de, por ejemplo, Schönhage como base para sus modelos RAM0 y RAM1 que conducen a su modelo de máquina de punteros SMM, también analizado brevemente en van Emde Boas (1990):

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

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

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

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

Definición formal

Una máquina contadora consta de:

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

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

Algunos modelos han atomizado aún más algunas de las instrucciones anteriores en instrucciones sin parámetros o las han combinado en una única instrucción, como "Decrementar" precedida por un salto condicional si es cero "JZ (r, z)". La atomización de las instrucciones o la inclusión de instrucciones de conveniencia no provoca cambios en el poder conceptual, ya que cualquier programa en una variante se puede traducir directamente a la otra.

En el suplemento Modelos de máquina-registro se analizan conjuntos de instrucciones alternativos .

Ejemplo: COPIAR el recuento del registro #2 al #3

Este ejemplo muestra cómo crear tres instrucciones más útiles: clear , unconditional jump y copy .

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

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

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

Condiciones iniciales

Inicialmente, el registro n.° 2 contiene "2". Los registros n.° 0, n.° 1 y n.° 3 están vacíos (contienen "0"). El registro n.° 0 permanece inalterado durante los cálculos porque se utiliza para el salto incondicional. El registro n.° 1 es un bloc de notas. El programa comienza con la instrucción 1.

Condiciones finales

El programa se detiene con el contenido del registro n.° 2 en su conteo original y el contenido del registro n.° 3 igual al contenido original del registro n.° 2, es decir,

[2] = [3].

Descripción de alto nivel del programa

El programa COPY ( #2, #3) tiene dos partes. En la primera parte, el programa mueve el contenido del registro fuente #2 tanto al bloc de notas #1 como al registro de destino #3; por lo tanto, #1 y #3 serán copias entre sí y del recuento original en #2, pero #2 se borra en el proceso de decrementarlo a cero. Los saltos incondicionales J (z) se realizan mediante pruebas del registro #0, que siempre contiene el número 0:

[#2] →#3; [#2] →#1; 0 →#2

En la segunda parte, el programa mueve (devuelve, restaura) el contenido del bloc de notas n.° 1 al n.° 2, borrando el bloc de notas n.° 1 en el proceso:

[#1] →#2; 0 →#1

Programa

El programa, resaltado en amarillo, se muestra escrito de izquierda a derecha en la parte superior derecha.

A continuación se muestra una "ejecución" del programa. El tiempo avanza por la página. Las instrucciones están en amarillo y los registros en azul. El programa está invertido 90 grados, con los números de instrucción (direcciones) en la parte superior, los mnemónicos de instrucción debajo de las direcciones y los parámetros de instrucción debajo de los mnemónicos (uno por celda):

Funciones recursivas parciales: construcción de "instrucciones de conveniencia" mediante recursión

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

Sin embargo, vemos que ADD habría sido posible, fácilmente. Y, de hecho, lo que sigue es un resumen de cómo pueden surgir las funciones recursivas primitivas como ADD, MULtiply y EXPonent (véase Boolos–Burgess–Jeffrey (2002) págs. 45-51).

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

{ J, DEC, INC, JZ, H }

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

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

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

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

Lo anterior es el conjunto de instrucciones de Shepherdson–Sturgis (1963).

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

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

• Defina "MULtiply(rj _, rk _, ri ₎ " (MUL) (quizás preservando el contenido de rj _, rk ₎ , en términos de lo anterior:

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

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

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

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

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

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

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

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

Problemas con el modelo de máquina contadora

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

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

(2) Números ilimitados de registros versus números limitados de instrucciones de máquina de estados: ¿Cómo accederá la máquina a registros con números de dirección que estén más allá del alcance/capacidad de su máquina de estados finitos?

(3) Los modelos totalmente reducidos son engorrosos:

Shepherdson y Sturgis (1963) no se disculpan por su conjunto de seis instrucciones. Hicieron su elección basándose en la "facilidad de programación... más que en la economía" (p. 219, nota al pie 1).

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

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

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

Las máquinas de dos contadores son equivalentes a Turing (con una salvedad)

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

Paso 1: Una máquina de Turing se puede simular mediante dos pilas.

Una máquina de Turing consta de una FSM y una cinta infinita, inicialmente llena de ceros, sobre la que la máquina puede escribir unos y ceros. En cualquier momento, el cabezal de lectura/escritura de la máquina apunta a una celda de la cinta. Esta cinta se puede cortar conceptualmente por la mitad en ese punto. Cada mitad de la cinta se puede tratar como una pila , donde la parte superior es la celda más cercana al cabezal de lectura/escritura, y la parte inferior está a cierta distancia del cabezal, con todos los ceros de la cinta más allá de la parte inferior. En consecuencia, una máquina de Turing se puede simular con una FSM más dos pilas. Mover el cabezal hacia la izquierda o hacia la derecha es equivalente a sacar un bit de una pila y empujarlo hacia la otra. Escribir es equivalente a cambiar el bit antes de empujarlo.

Paso 2: Una pila se puede simular mediante dos contadores.

Una pila que contiene ceros y unos puede ser simulada por dos contadores cuando los bits en la pila se consideran como la representación de un número binario (el bit más alto en la pila es el bit menos significativo). Introducir un cero en la pila es equivalente a duplicar el número. Introducir un uno es equivalente a duplicar y sumar 1. Hacer estallar es equivalente a dividir por 2, donde el resto es el bit que se ha hecho estallar. Dos contadores pueden simular esta pila, en la que uno de los contadores contiene un número cuya representación binaria representa los bits en la pila, y el otro contador se utiliza como un bloc de notas. Para duplicar el número en el primer contador, la FSM puede inicializar el segundo contador a cero, luego decrementar repetidamente el primer contador una vez e incrementar el segundo contador dos veces. Esto continúa hasta que el primer contador llega a cero. En ese punto, el segundo contador contendrá el número duplicado. La reducción a la mitad se realiza decrementando un contador dos veces e incrementando el otro una vez, y repitiendo hasta que el primer contador llega a cero. El resto se puede determinar según si llegó a cero después de un número par o impar de pasos, donde la paridad del número de pasos está codificada en el estado del FSM.

Paso 3: Cuatro contadores pueden ser simulados por dos contadores.

Como antes, uno de los contadores se utiliza como borrador. El otro contiene un entero cuya factorización prima es 2 ^a 3 ^b 5 ^c 7 ^d . Los exponentes a , b , c y d pueden considerarse como cuatro contadores virtuales que se están empaquetando (a través de la numeración de Gödel ) en un solo contador real. Si el contador real se establece en cero y luego se incrementa una vez, eso es equivalente a establecer todos los contadores virtuales a cero. Si el contador real se duplica, eso es equivalente a incrementar a , y si se reduce a la mitad, eso es equivalente a decrementar a . Por un procedimiento similar, se puede multiplicar o dividir por 3, lo que es equivalente a incrementar o decrementar b . De manera similar, c y d se pueden incrementar o decrementar. Para verificar si un contador virtual como c es igual a cero, simplemente divida el contador real por 5, vea cuál es el resto, luego multiplique por 5 y agregue nuevamente el resto. Eso deja el contador real sin cambios. El resto habrá sido distinto de cero si y sólo si c era cero.

Como resultado, una FSM con dos contadores puede simular cuatro contadores, que a su vez simulan dos pilas, que simulan una máquina de Turing. Por lo tanto, una FSM más dos contadores es al menos tan potente como una máquina de Turing. Una máquina de Turing puede simular fácilmente una FSM con dos contadores, por lo tanto, las dos máquinas tienen una potencia equivalente.

La advertencia: *Si* sus contadores se inicializan anortey 0, entonces un 2CM no puede calcular 2norte

Este resultado, junto con una lista de otras funciones de N que no son calculables por una máquina de dos contadores —cuando se inicializa con N en un contador y 0 en el otro— como N ² , sqrt( N ), log ₂ ( N ), etc., aparece en un artículo de Schroeppel (1972). El resultado no es sorprendente, porque el modelo de máquina de dos contadores fue probado (por Minsky) como universal solo cuando el argumento N se codifica apropiadamente (por Gödelización) para simular una máquina de Turing cuya cinta inicial contiene N codificado en unario; además, la salida de la máquina de dos contadores se codificará de manera similar. Este fenómeno es típico de bases de computación muy pequeñas cuya universalidad se prueba solo por simulación (por ejemplo, muchos tarpits de Turing , las máquinas de Turing universales más pequeñas conocidas , etc.).

La prueba está precedida por algunos teoremas interesantes:

• "Teorema: Una máquina de tres contadores puede simular una máquina de Turing" (p. 2, cf también Minsky 1967:170-174)
• "Teorema: Una 3CM [máquina de tres contadores] puede calcular cualquier función recursiva parcial de una variable. Comienza con el argumento [es decir, N ] en un contador y (si se detiene) deja la respuesta [es decir, F( N )] en un contador". (p. 3)
• "Teorema: Una máquina contadora puede ser simulada por una 2CM [máquina de dos contadores], siempre que se acepte una codificación oscura para la entrada y la salida" [p. 3; la "codificación oscura" es: 2 ^W 3 ^X 5 ^Y 7 ^Z donde los contadores simulados son W, X, Y, Z]
• "Teorema: Cualquier máquina contadora puede ser simulada por un 2CM, siempre que se acepte una codificación oscura para la entrada y la salida." (p. 3)
  • "Corolario: el problema de detención de los 2CM es irresoluble.
  • "Corolario: Un 2CM puede calcular cualquier función recursiva parcial de un argumento, siempre que la entrada esté codificada como 2 ^N y la salida (si la máquina se detiene) esté codificada como 2 ^respuesta ." (p. 3)
• "Teorema: No existe ninguna máquina con dos contadores que calcule 2 ^N [si un contador se inicializa en N ]". (p. 11)

En relación con el segundo teorema, que dice que “una máquina de 3 CM puede calcular cualquier función recursiva parcial”, el autor desafía al lector con un “problema difícil: multiplicar dos números utilizando sólo tres contadores” (p. 2). La prueba principal implica la noción de que las máquinas de dos contadores no pueden calcular secuencias aritméticas con tasas de crecimiento no lineales (p. 15), es decir, “la función 2 ^X crece más rápidamente que cualquier progresión aritmética” (p. 11).

Un ejemplo práctico de cálculo mediante conteo

La calculadora Friden EC-130 no tenía lógica sumadora como tal. Su lógica era altamente serial, haciendo aritmética contando. Internamente, los dígitos decimales eran de base 1; por ejemplo, un seis se representaba con seis pulsos consecutivos dentro del intervalo de tiempo asignado para ese dígito. Cada intervalo de tiempo contenía un dígito, el menos significativo primero. Los acarreos activaban un flip-flop que hacía que se añadiera un recuento al dígito en el siguiente intervalo de tiempo.

La suma se hacía mediante un contador ascendente, mientras que la resta se hacía mediante un contador descendente, con un esquema similar para tratar los préstamos.

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

Véase también

• Máquina de puntero
• Máquina post-Turing
• Máquina de acceso aleatorio
• Registrar máquina
• Máquina B de Wang
• Sistema de adición de vectores

Referencias

1. John E. Hopcroft y Rajeev Motwani y Jeffrey D. Ullman (2003). Introducción a la teoría de autómatas, lenguajes y computación . Addison Wesley. pág. 352. ISBN 0-201-44124-1.
2. Boolos–Burgess–Jeffrey (2002)

• George Boolos , John P. Burgess , Richard Jeffrey (2002), Computability and Logic: Fourth Edition , Cambridge University Press, Cambridge, Inglaterra. El texto original de Boolos-Jeffrey ha sido revisado extensamente por Burgess: es más avanzado que un libro de texto introductorio. El modelo de "máquina de ábaco" se desarrolla extensamente en el Capítulo 5 Computabilidad del ábaco ; es uno de los tres modelos tratados y comparados extensamente: la máquina de Turing (aún en la forma original de 4 tuplas de Boolos) y la recursión, los otros dos.
• Arthur Burks , Herman Goldstine , John von Neumann (1946), Discusión preliminar del diseño lógico de un instrumento de computación electrónica , reimpreso págs. 92 y siguientes en Gordon Bell y Allen Newell (1971), Estructuras de computadora: lecturas y ejemplos , McGraw-Hill Book Company, Nueva York. ISBN 0-07-004357-4 . 
• Stephen A. Cook y Robert A. Reckhow (1972), Máquinas de acceso aleatorio con límites de tiempo , Journal of Computer Systems Science 7 (1973), 354–375.
• Martin Davis (1958), Computabilidad e insolubilidad , McGraw-Hill Book Company, Inc. Nueva York.
• Calvin Elgot y Abraham Robinson (1964), Random-Access Stored-Program Machines, an Approach to Programming Languages , Revista de la Asociación para Maquinaria Computacional, Vol. 11, Núm. 4 (octubre de 1964), págs. 365–399.
• Fischer, Patrick C. ; Meyer, AR ; Rosenberg, Arnold L. (1968), "Máquinas de contraataque y lenguajes de contraataque", Mathematical Systems Theory , 2 (3): 265–283, doi :10.1007/bf01694011, MR  0235932, S2CID  13006433Desarrolla teoremas de jerarquía temporal y espacial para máquinas contadoras, análogos a las jerarquías para las máquinas de Turing.
• J. Hartmanis (1971), "Complejidad computacional de máquinas de programas almacenados de acceso aleatorio", Mathematical Systems Theory 5, 3 (1971) págs. 232–245.
• Hopcroft, John; Jeffrey Ullman (1979). Introducción a la teoría de autómatas, lenguajes y computación (1.ª ed.). Reading Mass: Addison-Wesley. ISBN 0-201-02988-X.Un libro difícil centrado en cuestiones de interpretación de "lenguajes" por parte de máquinas, NP-Completitud, etc.
• Stephen Kleene (1952), Introducción a las metamatemáticas , North-Holland Publishing Company, Ámsterdam, Países Bajos. ISBN 0-7204-2103-9 . 
• Donald Knuth (1968), The Art of Computer Programming , 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 trabaja con estructuras enlazadas".
• Joachim Lambek (1961, recibido el 15 de junio de 1961), How to Program an Infinite Abacus , Mathematical Bulletin, 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) Introduction to Metamathematics .
• ZA Melzak (1961, recibido el 15 de mayo de 1961), Un enfoque aritmético informal de la computabilidad y la computación , Canadian Mathematical Bulletin , vol. 4, núm. 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 Laboratorios de telefonía Bell y con el Dr. H. Wang de la Universidad de Oxford".
• Marvin Minsky (1961). "Insolubilidad recursiva del problema de Post de la "etiqueta" y otros temas de la teoría de las máquinas de Turing". Anales de Matemáticas . 74 (3): 437–455. doi :10.2307/1970290. JSTOR  1970290.
• Marvin Minsky (1967). Computación: máquinas finitas e infinitas (1.ª ed.). Englewood Cliffs, NJ: Prentice-Hall, Inc.En particular, véase el capítulo 11: Modelos similares a las computadoras digitales y el capítulo 14: Bases muy simples para la computabilidad . En el primer capítulo define "máquinas de programa" y en el capítulo posterior analiza las "máquinas de programa universales 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 for Computing Machinery (JACM) 10:217-255, 1963. Un documento de referencia extremadamente valioso. En su Apéndice A, los autores citan otros 4 con referencia a "Minimalidad de instrucciones utilizadas en 4.1: comparación con sistemas similares".
  • Kaphengst, Heinz, Eine Abstrakte programmgesteuerte Rechenmaschine' , Zeitschrift fur mathematische Logik und Grundlagen der Mathematik: 5 (1959), 366-379.
  • Ershov, AP On operator algorithms , (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 . Matemáticas-Física. Semesterberichte (Göttingen) 4 (1954), 42–53.
• A. Schönhage (1980), Storage Modification Machines , Society for Industrial and Applied Mathematics, SIAM J. Comput. Vol. 9, No. 3, agosto de 1980. En donde Schönhage muestra la equivalencia de su SMM con la "sucesora RAM" (Random Access Machine), etc.
• Rich Schroeppel , mayo de 1972, "Una máquina de dos contadores no puede calcular 2 ^N ", Instituto Tecnológico de Massachusetts, Laboratorio de IA, Memorándum sobre Inteligencia Artificial n.° 257. El autor hace referencia a Minsky 1967 y señala que " Frances Yao demostró de forma independiente la no computabilidad utilizando un método similar en abril de 1971".
• Peter van Emde Boas , Modelos de máquinas y simulaciones, págs. 3–66, que aparece en:

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

El tratamiento que van Emde Boas hace de los SMM aparece en las páginas 32-35. Este tratamiento aclara el planteamiento de Schōnhage de 1980: sigue de cerca el tratamiento de Schōnhage, pero lo amplía ligeramente. Es posible que se necesiten ambas referencias para una comprensión eficaz.

• Hao Wang (1957), Una variante de la teoría de Turing sobre las máquinas de computación , JACM (Revista de la Asociación de Maquinaria de Computación) 4; 63–92. Presentado en la reunión de la Asociación, 23–25 de junio de 1954.
• ^[1]

Enlaces externos

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

1. "Copia archivada" (PDF) . stedolan.net . Archivado desde el original (PDF) el 14 de febrero de 2021.{{cite web}}: CS1 maint: copia archivada como título ( enlace )