maquina contadora

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

Una contramáquina o contraautómata es una máquina abstracta utilizada en lógica formal e informática teórica para modelar la computación . Es el más primitivo de los cuatro tipos de máquinas registradoras . Una máquina contadora comprende un conjunto de uno o más registros ilimitados , cada uno de los cuales puede contener un único número entero no negativo, y una lista de instrucciones aritméticas y de control (generalmente secuenciales) que debe seguir la máquina. 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 usa de esta manera, la máquina contadora se usa 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 eviten el entrelazamiento, la operación de escritura simultánea por dos (o más) subprocesos en la misma dirección de memoria.

Las máquinas contadoras con tres contadores pueden calcular cualquier función recursiva parcial de una sola variable. Las máquinas contadoras 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 contadoras con un solo contador pueden reconocer un superconjunto adecuado de lenguajes regulares y un subconjunto de lenguajes deterministas libres de contexto . ^[1]

Caracteristicas basicas

Para un determinado modelo de máquina contadora, el conjunto de instrucciones es pequeño: de una a seis o siete instrucciones. La mayoría de los modelos contienen algunas operaciones aritméticas y al menos una operación condicional (si la condición es verdadera, entonces salta). Tres modelos básicos , cada uno con tres instrucciones, se extraen de la siguiente colección. (Las abreviaturas son arbitrarias).

• CLR (r): registro CLeaR r . (Establezca r en cero).
• INC (r): INCrementa el contenido del registro r .
• DEC (r): DEcrementa el contenido del registro r .
• CPY (r _j , r _k ): CoPY 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 Saltar a la instrucción z ELSE continuar en secuencia.
• JE (r _j , r _k , z): SI el contenido del registro r _j es igual al contenido del registro r _k ENTONCES Saltar a la instrucción z ELSE continuar en secuencia.

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

Utilizando las instrucciones mencionadas anteriormente, varios autores han comentado determinadas 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) interpretado por 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 base de máquinas contadoras tienen la misma potencia de cálculo ya que las instrucciones de un modelo se pueden derivar de las de otro. Todos son equivalentes al poder computacional de las máquinas de Turing . Debido a su estilo de procesamiento único, las máquinas contadoras suelen ser exponencialmente más lentas que las máquinas de Turing comparables.

Nombres alternativos, modelos alternativos.

Los modelos de máquinas de mostrador reciben distintos nombres 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í, salte a la instrucción I _z ; de lo contrario, DISMINUYA el contenido de r:

• Máquina de Shepherdson-Sturgis , porque estos autores establecieron formalmente su modelo en una exposición de fácil acceso (1963). Utiliza el conjunto de instrucciones (1) aumentado con instrucciones de conveniencia adicionales (JNZ es "Jump if Not Zero, usado 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 usa el conjunto de instrucciones (1), pero la ejecución de instrucciones no es secuencial por defecto, por lo que el parámetro adicional 'z' aparece para 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 programa , computadora de programa , los nombres que Minsky (1967) dio al modelo porque, al igual que una computadora, sus instrucciones proceden secuencialmente a menos que un salto condicional tenga éxito. Utiliza (normalmente) el conjunto de instrucciones (1), pero puede ampliarse de forma similar al modelo Shepherson-Sturgis. JZDEC a menudo se divide:

  { 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 como lo llama Boolos-Burgess-Jeffrey (2002). 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 de Lambek , un nombre alternativo que Boolos-Burgess-Jeffrey (2002) le dio a la máquina de ábaco. Utiliza un conjunto de instrucciones (reducido en 1) 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 RAM sucesor . Utiliza el conjunto de instrucciones (2) de, por ejemplo, Schönhage como base para sus modelos RAM0 y RAM1 que conducen a su modelo SMM de máquina de puntero , también discutido 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). (Aumentaron el mismo modelo con direccionamiento indirecto mediante el uso de un registro adicional que se utilizará como registro "índice").

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

• Otras máquinas contadoras : Minsky (1967) demuestra cómo construir los tres modelos base (programa/Minsky/Lambek-abacus, 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 "suma" y "resta" en lugar de "incremento" y "disminución". Las pruebas de Minsky (1961, 1967) de que un solo registro será suficiente para la equivalencia de Turing requieren 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 aún es necesario para demostrar la equivalencia de Turing ; también demostrado en Elgot-Robinson 1964).

Definicion formal

Una máquina contadora consta de:

1. Registros etiquetados con valores enteros ilimitados : 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 hacen 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 ejecutará. Este registro es finito y está separado de los registros anteriores; Así, el modelo de contramáquina es un ejemplo de la arquitectura de Harvard.
3. Lista de instrucciones secuenciales etiquetadas : 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 de computadora, las instrucciones se enumeran en orden secuencial; A menos que el salto sea exitoso, la secuencia predeterminada continúa en orden numérico. Cada una de las instrucciones de la lista proviene de un conjunto (muy) pequeño, pero este conjunto no incluye la dirección indirecta. Históricamente, la mayoría de los modelos extrajeron sus instrucciones de este conjunto:

{ Incrementar (r), Disminuir (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 anteriores en instrucciones sin parámetros o las han combinado en una sola instrucción como "Decremento" precedida por un salto condicional si cero "JZ (r, z)". La atomización de instrucciones o la inclusión de instrucciones de conveniencia no provoca ningún cambio en el poder conceptual, ya que cualquier programa en una variante puede traducirse directamente a la otra.

Los conjuntos de instrucciones alternativos se analizan en el suplemento Modelos de máquinas de registro .

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

Este ejemplo muestra cómo crear tres instrucciones más útiles: borrar , salto incondicional y copiar .

• 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 )

Después, 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 como se define aquí:

Condiciones iniciales

Inicialmente, el registro n.º 2 contiene "2". Los registros #0, #1 y #3 están vacíos (contienen "0"). El registro 0 permanece sin cambios 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 recuento 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 de origen n.° 2 tanto al bloc de notas n.° 1 como al registro de destino n.° 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 disminuirlo 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 scratch-pad #1 de regreso al scratch-pad #2, limpiando el scratch-pad #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 corre por la página. Las instrucciones están en amarillo, los registros en azul. El programa está volteado 90 grados, con los números de instrucción (direcciones) en la parte superior, los mnemotécnicos de instrucción debajo de las direcciones y los parámetros de instrucción debajo de los mnemotécnicos (uno por celda):

Las funciones recursivas parciales: creación de "instrucciones de conveniencia" mediante recursividad

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 #3 hubiera tenido contenido inicialmente, la suma de los contenidos de #2 y #3 habría terminado en #3. Entonces, para ser completamente preciso, el programa CPY debería haber precedido sus movimientos con CLR (1) y CLR (3).

Sin embargo, sí vemos que el TDA habría sido posible fácilmente. Y, de hecho, lo siguiente es un resumen de cómo pueden surgir las funciones recursivas primitivas como SUMA, MULTIPLICAR y EXPonente (ver Boolos–Burgess–Jeffrey (2002) p. 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, DIC, INC, JZ, H}

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

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

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

{CPY, CLR, J, DIC, 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:

{AÑADIR, CPY, CLR, J, DIC, INC, JZ, H}

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

{MUL, AÑADIR, CPY, CLR, J, DIC, INC, JZ, H}

• Defina "EXPonencial (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, AGREGAR, CPY, CLR, J, DEC, INC, JZ, H }

En general, podemos construir cualquier función recursiva primitiva parcial o total que deseemos, utilizando los mismos métodos. De hecho, Minsky (1967), Shepherdson-Sturgis (1963) y Boolos-Burgess-Jeffrey (2002) dan 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é pasa con la equivalencia total de Turing ? Necesitamos agregar el sexto operador, el operador μ , para obtener la equivalencia completa, capaz de crear las funciones recursivas total y parcial :

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 básicos disponibles (1, 2 o 3) (se puede encontrar un ejemplo en el operador μ ). Esto significa que cualquier función mu recursiva se puede implementar como una máquina contadora, ^[2] a pesar del conjunto finito de instrucciones y el tamaño del programa del diseño de la máquina contadora. Sin embargo, la construcción requerida puede ser contraria a la intuición, 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 determinada 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 a 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 manera sencilla. Pero la función no es recursiva primitiva. Uno puede verse tentado a implementar el operador de flecha hacia arriba usando una construcción similar a las instrucciones anteriores de sucesor, suma, multiplicación y exponenciación, implementando una pila de llamadas para que la función se pueda aplicar de forma recursiva 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 utilizar un número ilimitado de registros en su cálculo, lo que sería necesario para implementar una pila de llamadas que pueda crecer arbitrariamente. La operación de flecha hacia arriba aún se puede implementar como una máquina contadora ya que es muy 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 los registros con números de direcciones 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. Han hecho su elección basándose en "la facilidad de programación... más que en la economía" (p. 219, nota 1 al pie de página).

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

• • INCREMENTO (r); [r] +1 → r
  • DECREMENTO (r); [r] -1 → r
  • CLARO (r); 0 → r
  • COPIAR (r _s a rd ₎ ; [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 se puede construir una "Máquina de Programa Universal" con sólo dos registros (p. 255 y siguientes).

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

Para cada máquina de Turing , existe un 2CM que la simula, dado que la entrada y salida del 2CM están codificadas adecuadamente. 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. En primer lugar, una máquina de Turing puede simularse mediante una máquina de estados finitos (FSM) equipada con dos pilas. Luego, se pueden simular dos pilas con cuatro fichas. Finalmente, dos contadores pueden simular cuatro contadores. La máquina de dos contadores utiliza el conjunto de instrucciones {INC (r, z), JZDEC (r, z _verdadero , z _falso )}.

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

Una máquina de Turing consta de un FSM y una cinta infinita, inicialmente llena de ceros, sobre la cual 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 en la cinta más allá de la parte inferior. En consecuencia, una máquina de Turing puede simularse mediante un FSM más dos pilas. Mover la cabeza hacia la izquierda o hacia la derecha equivale a sacar un trozo de una pila y empujarlo hacia la otra. Escribir equivale a cambiar el bit antes de empujarlo.

Paso 2: Se puede simular una pila con dos contadores.

Una pila que contiene ceros y unos se puede simular mediante dos contadores cuando se considera que los bits de la pila representan un número binario (el bit superior de la pila es el bit menos significativo). Colocar un cero en la pila equivale a duplicar el número. Empujar un uno equivale a duplicar y sumar 1. Hacer estallar es equivalente a dividir por 2, donde el resto es el bit que se hizo 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 de la pila y el otro contador se utiliza como bloc de notas. Para duplicar el número en el primer contador, el FSM puede inicializar el segundo contador a cero, luego disminuir 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 momento, la segunda ficha contendrá el número duplicado. La reducción a la mitad se realiza disminuyendo un contador dos veces e incrementando el otro una vez, y repitiendo hasta que el primer contador llegue a cero. El resto se puede determinar en función de si alcanzó 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: Se pueden simular cuatro contadores mediante dos contadores.

Como antes, una de las fichas se utiliza como bloc de notas. El otro contiene un número 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 empaquetan (mediante la numeración de Gödel ) en un único contador real. Si el contador real se pone a cero y luego se incrementa una vez, eso equivale a poner todos los contadores virtuales a cero. Si el contador real se duplica, equivale a incrementar a , y si se reduce a la mitad, equivale a disminuir a . Por un procedimiento similar, se puede multiplicar o dividir por 3, lo que equivale a incrementar o disminuir b . De manera similar, cyd se pueden incrementar o disminuir. Para comprobar 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 vuelva a sumar el resto. Eso deja el contador real sin cambios. El resto habrá sido distinto de cero si y sólo si c fuera cero.

Como resultado, un 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, un FSM más dos contadores es al menos tan poderoso como una máquina de Turing. Una máquina de Turing puede simular fácilmente un FSM con dos contadores, por lo que las dos máquinas tienen potencia equivalente.

La advertencia: *Si* sus contadores se inicializan en N y 0, entonces un 2CM no puede calcular 2 N

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 Minsky demostró que el modelo de máquina de dos contadores es universal sólo cuando el argumento N está codificado apropiadamente (mediante 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 estará codificada de manera similar. Este fenómeno es típico de bases de cálculo muy pequeñas cuya universalidad se prueba sólo mediante simulación (por ejemplo, muchos tarpits de Turing , las máquinas universales de Turing más pequeñas conocidas , etc.).

La demostración está precedida por algunos teoremas interesantes:

• "Teorema: una máquina de tres contadores puede simular una máquina de Turing" (p. 2, también cf. 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 mostrador." (pág. 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 simularse con un 2CM, siempre que se acepte una codificación oscura para la entrada y la salida." (pág. 3)
  • "Corolario: el problema de la detención de los 2CM no tiene solución.
  • "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ág. 3)
• "Teorema: No existe una máquina con dos contadores que calcule 2 ^N [si un contador se inicializa en N ]". (pág.11)

Con respecto al segundo teorema de que "Un 3CM puede calcular cualquier función recursiva parcial", el autor desafía al lector con un "Problema difícil: multiplicar dos números usando 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ág. 11).

Un ejemplo práctico de cálculo contando.

La calculadora Friden EC-130 no tenía lógica sumadora como tal. Su lógica era muy serializada y hacía aritmética contando. Internamente, los dígitos decimales eran base-1; por ejemplo, un seis estaba representado por seis pulsos consecutivos dentro del intervalo de tiempo asignado para ese dígito. Cada intervalo de tiempo tenía un dígito, el menos significativo primero. Los acarreos establecieron un flip-flop que provocó que se agregara un conteo al dígito en el siguiente intervalo de tiempo.

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

El esquema de intervalo de tiempo definió 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, el EC-132, restaba efectivamente números enteros impares consecutivos, y cada disminución requería dos restas consecutivas. Después del primero, el minuendo se incrementaba en uno antes de la segunda resta.

Ver también

• máquina de puntero
• Máquina post-Turing
• Máquina de acceso aleatorio
• Registrar maquina
• Máquina Wang B
• Sistema de suma de vectores

Referencias

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

• 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.
• Arthur Burks , Herman Goldstine , John von Neumann (1946), Discusión preliminar del 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 , Libro McGraw-Hill Compañía, Nueva York. ISBN 0-07-004357-4 . 
• 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.
• Martin Davis (1958), Computabilidad e insolvabilidad , McGraw-Hill Book Company, Inc. Nueva York.
• 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.
• Fischer, Patrick C .; Meyer, AR ; Rosenberg, Arnold L. (1968), "Contadora de máquinas y contralenguajes", Teoría de sistemas matemáticos , 2 (3): 265–283, doi :10.1007/bf01694011, MR  0235932, S2CID  13006433. Desarrolla teoremas de jerarquía temporal y espacial para contramáquinas, análogos a las jerarquías de las máquinas de Turing.
• J. 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.
• Hopcroft, John; Jeffrey Ullman (1979). Introducción a la teoría, los lenguajes y la computación de autómatas (1ª ed.). Misa de lectura: Addison-Wesley. ISBN 0-201-02988-X.Un libro difícil centrado en las cuestiones de la interpretación automática de "lenguajes", la integridad NP, etc.
• Stephen Kleene (1952), Introducción a las metamatemáticas , North-Holland Publishing Company, Amsterdam, Países Bajos. ISBN 0-7204-2103-9 . 
• 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".
• Joachim Lambek (1961, recibido el 15 de junio de 1961), Cómo programar un ábaco infinito , Mathematical Bulletin, vol. 4, núm. 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), An informal Arithmetical Approach to Computability and Computation , 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 Drs. R. Hamming, D. McIlroy y V. Vyssots de Bell Telephone Laborators y con el Dr. H. Wang de la Universidad de Oxford".
• Marvin Minsky (1961). "Insolvencia recursiva del problema de la" etiqueta "de Post y otros temas en 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, 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 Computability of Recursive Functions de diciembre de 1961 , Journal of the Association for 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 "Minimidad 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 Sobre algoritmos de operador , (ruso) Dok. Akád. Nauk 122 (1958), 967-970. Traducción al inglés, Automat. Expreso 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), 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.
• 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, Memorándum de 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 y simulaciones de máquinas, págs. 3–66, que aparece 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). Garantía de calidad 76.H279 1990. 

El tratamiento que hace van Emde Boas de las 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.

• 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.
• ^[1]

enlaces externos

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

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