Algunos tipos particulares de máquinas de puntero se denominan autómata de enlace, máquina KU, SMM, máquina LISP atomística, máquina de puntero de árbol, etc. [2]
Las máquinas de puntero no tienen instrucciones aritméticas. La computación procede únicamente leyendo los símbolos de entrada, modificando y realizando varias pruebas en su estructura de almacenamiento (el patrón de nodos y punteros) y generando símbolos basados en las pruebas. En este sentido, el modelo es similar a la máquina de Turing .
Tipos de "máquinas de puntero"
Tanto Gurevich como Ben-Amram enumeran una serie de modelos "atomistas" muy similares de "máquinas abstractas"; [3] [2] Ben-Amram cree que los "modelos atomistas" deben distinguirse de los modelos de "alto nivel". A continuación se presentarán los siguientes modelos atomísticos:
Máquinas de modificación de almacenamiento de Schönhage (SMM), [4]
Máquinas Kolmogorov-Uspenskii (KUM o KU-Machines). [5]
Ben-Amram también presenta las siguientes variedades, que no se analizan más en este artículo:
Máquina atomística LISP pura (APLM)
Máquina atomística LISP completa (AFLM),
Máquinas de puntero atomístico generales,
Lenguaje I de Jones (dos tipos).
Modelo de máquina de modificación de almacenamiento (SMM) de Schönhage
La siguiente presentación sigue a van Emde Boas. [6]
La máquina consta de un alfabeto fijo de símbolos de entrada, un programa fijo y un gráfico dirigido mutable con sus flechas etiquetadas por símbolos alfabéticos. El gráfico es el almacenamiento de la máquina . Cada nodo del gráfico tiene exactamente una flecha de salida etiquetada con cada símbolo, aunque algunas de ellas pueden regresar al nodo original. Un nodo fijo del gráfico se identifica como nodo inicial o "activo".
Luego, cada palabra de los símbolos del alfabeto se puede traducir a un camino a través de la máquina; por ejemplo, 10011 se traduciría en tomar el borde 1 del nodo inicial, luego el borde 0 del nodo resultante, luego el borde 0, luego el borde 1, luego el borde 1. Por lo tanto, una palabra identifica un nodo, el nodo final de la ruta, pero esta identificación cambiará a medida que cambie el gráfico durante el cálculo.
La máquina puede recibir instrucciones que cambian el diseño del gráfico. Las instrucciones básicas son:
(1) nueva instrucción w , que crea un nuevo nodo al final de la ruta w , con todos sus bordes dirigidos al penúltimo nodo en w . (2) establezca la instrucción w a v que (re) dirige un borde a un nodo diferente. Aquí w y v representan palabras . La instrucción da como resultado cambiar el destino del último borde en la ruta w .
Algunos pasos en la ejecución de una máquina {0,1} de 2 símbolos con instrucciones: (1) new ε; (2) nuevo 1; (3) nuevo 11. La instrucción n.° 1 inicializa el gráfico de almacenamiento como un único nodo, el nodo 1, en el gráfico de almacenamiento.
(3) Si v = w entonces instrucción z : Instrucción condicional que compara dos caminos representados por las palabras w y v para ver si terminan en el mismo nodo; Si es así, salte a la instrucción z ; de lo contrario, continúe. Esta instrucción tiene el mismo propósito que el comando if en cualquier lenguaje de programación imperativo.
Evolución del gráfico de almacenamiento en una máquina {0,1} de 2 símbolos con instrucciones: (1) nuevo ε; (2) nuevo 1; (3) nuevos 11; (4) nuevos 10; (5) establezca 111 en 10. En este momento, si la máquina hiciera si 10 = 111 y luego xxx, entonces la prueba sería exitosa y la máquina efectivamente saltaría a xxx.
(4) leer y escribir instrucciones de entrada/salida, accediendo a una cinta de entrada de sólo lectura y a una cinta de salida de sólo escritura, ambas con símbolos del alfabeto.
Modelo de máquina Kolmogorov-Uspenskii (máquina KU)
KUM se diferencia de SMM en que solo permite punteros invertibles: para cada puntero de un nodo x a un nodo y, debe estar presente un puntero inverso de y a x, etiquetado con el mismo símbolo. En otras palabras, el gráfico de almacenamiento no está dirigido. Dado que los punteros salientes deben estar etiquetados con símbolos distintos del alfabeto, tanto los gráficos KUM como SMM tienen un grado de salida O(1). Sin embargo, la invertibilidad de los punteros KUM también restringe el grado de entrada a O (1). Esto aborda algunas preocupaciones sobre el realismo físico (en contraposición al puramente informativo).
Hay otras diferencias menores entre los modelos, como la forma del programa: una tabla de estado en lugar de una lista de instrucciones.
Consideraciones sobre el modelo de máquina puntero
Uso del modelo en la teoría de la complejidad : van Emde Boas (1990) expresa su preocupación de que esta forma de modelo abstracto sea:
"un modelo teórico interesante, pero... su atractivo como modelo fundamental para la teoría de la complejidad es cuestionable. Su medida del tiempo se basa en el tiempo uniforme en un contexto donde se sabe que esta medida subestima la verdadera complejidad del tiempo. La misma observación es válida para la medida del espacio para la máquina" (van Emde Boas (1990) p. 35)
Gurevich también expresa preocupación:
"Hablando pragmáticamente, el modelo de Schönhage proporciona una buena medida de la complejidad temporal en el estado actual de la técnica (aunque preferiría algo parecido a las computadoras de acceso aleatorio de Angluin y Valiant)". [7]
Schönhage demuestra las equivalencias en tiempo real de dos tipos de máquinas de acceso aleatorio con el SMM. [4]
Algoritmos en el modelo SMM : Schönhage demuestra que el SMM puede realizar multiplicaciones de enteros en tiempo lineal. [4]
Usos potenciales del modelo : Gurevich se pregunta si una máquina KU paralela "se parece un poco al cerebro humano" [8]
Computación paralela : Todos los modelos mencionados anteriormente son secuenciales. Cook y Dymond propusieron un modelo de máquina de puntero paralelo (atómico); [9] también se ha utilizado un modelo de máquina de puntero paralelo de alto nivel (no atomista) [10]
Máquina de contador : la máquina más primitiva, los conjuntos de instrucciones de los modelos base se utilizan en toda la clase de máquinas de registro.
Máquina post-Turing : máquina minimalista de una cinta, dos direcciones, 1 símbolo {espacio en blanco, marca} similar a Turing pero con ejecución de instrucciones secuencial predeterminada de manera similar a las máquinas contadoras básicas de 3 instrucciones.
Otras lecturas
La mayoría de las referencias y una bibliografía se encuentran en el artículo Registrar máquina . Lo siguiente es particular de este artículo:
Amir Ben-Amram (1995), ¿Qué es una "máquina de puntero"?, SIGACT News (ACM Special Interest Group on Automata and Computability Theory)", volumen 26, 1995. Donde Ben-Amram describe los tipos y subtipos: (tipo 1a ) Máquinas abstractas: modelos atomísticos que incluyen las máquinas Kolmogorov-Uspenskii (KUM), las máquinas de modificación de almacenamiento (SMM) de Schönhage, el "autómata de enlace" de Knuth, APLM y AFLM (máquina atomística Pure-LISP) y (máquina atomística Full-LISP), atomística general. Máquinas de Puntero, Lenguaje I de Jones; (tipo 1b) Máquinas Abstractas: Modelos de alto nivel, (tipo 2) Algoritmos de puntero.
Yuri Gurevich (2000), Máquinas de estados abstractos secuenciales que capturan algoritmos secuenciales , Transacciones ACM sobre lógica computacional, vol. 1, núm. 1, (julio de 2000), páginas 77–111. En una sola frase, Gurevich compara las "máquinas de modificación de almacenamiento" de Schönhage [1980] con las "máquinas de puntero" de Knuth. Para más información, modelos similares como "máquinas de acceso aleatorio" hace referencia a Gurevich:
John E. Savage (1998), Modelos de computación: exploración del poder de la computación. Addison Wesley Longman.
Yuri Gurevich (1988), Sobre las máquinas de Kolmogorov y cuestiones relacionadas, columna sobre "Lógica en informática", Boletín de la Asociación europea de informática teórica, número 35, junio de 1988, 71-82. Se presentó la descripción unificada de las máquinas de Schönhage y Kolmogorov-Uspenskii utilizadas aquí.
Arnold Schönhage (1980), Máquinas de modificación de almacenamiento , Sociedad de Matemáticas Industriales y Aplicadas, SIAM J. Comput. vol. 9, No. 3, agosto de 1980. Donde Schönhage muestra la equivalencia de su SMM con la "RAM sucesora" (Random Access Machine), etc. Se refiere a un artículo anterior donde presenta el SMM:
Arnold Schönhage (1970), Universelle Turing Speicherung , Automatentheorie und Formale Sprachen, Dörr, Hotz, eds. Bibliografía. Instituto, Mannheim, 1970, págs. 69–383.
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).
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.
Referencias
^ Cloteaux, Brian; Ranjan, Desh (2006). "Algunos resultados de separación entre clases de algoritmos de puntero".
^ ab Amir Ben-Amram (1995). ¿Qué es una "máquina de puntero"?, SIGACT News (Grupo de interés especial de ACM sobre autómatas y teoría de la computabilidad), volumen 26, 1995.
^ Yuri Gurevich (2000), Máquinas de estados abstractos secuenciales capturan algoritmos secuenciales , Transacciones ACM sobre lógica computacional, vol. 1, núm. 1, (julio de 2000), páginas 77–111.
^ abcd Arnold Schönhage (1980), Máquinas de modificación de almacenamiento , SIAM Journal on Computing vol. 9, núm. 3, agosto de 1980.
^ Andrey Kolmogorov y V. Uspenskii , Sobre la definición de un algoritmo, Uspekhi Mat. Nauk 13 (1958), 3-28. Traducción al inglés en Traducciones de la American Mathematical Society, Serie II, Volumen 29 (1963), págs.
^ Peter van Emde Boas , Simulaciones y modelos de máquinas págs. 3–66 en: Jan van Leeuwen , ed. Manual de informática teórica. Volumen A: Algoritmos y Complejidad , The MIT PRESS/Elsevier, 1990. ISBN 0-444-88071-2 (volumen A).
^ Gurevich (1988) pág. 6 con referencia a Angluin D. y Valiant LG, "Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings", Journal of Computer and System Sciences 18 (1979) 155-193.
^ Yuri Gurevich (1988), Sobre las máquinas Kolmogorov y cuestiones relacionadas, la columna sobre "Lógica en la informática", Boletín de la Asociación europea de informática teórica, número 35, junio de 1988, 71-82.
^ Cocinero, Stephen A.; Dymond, Patrick W. (marzo de 1993). "Máquinas de puntero paralelo". Complejidad computacional . 3 : 19–30. doi :10.1007/BF01200405.
^ Goodrich, MT; Kosaraju, SR (1996). "Clasificación en una máquina de puntero paralelo con aplicaciones para configurar la evaluación de expresiones". Revista de la ACM . 43 (2): 331–361. doi :10.1145/226643.226670.
