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 punteros no tienen instrucciones aritméticas. El cálculo se realiza únicamente leyendo símbolos de entrada, modificando y realizando diversas pruebas en su estructura de almacenamiento (el patrón de nodos y punteros) y generando símbolos de salida en función de 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 presentan los siguientes modelos atomistas:
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 de LISP puro (APLM)
Máquina atomística full-LISP (AFLM),
Máquinas de puntero atomístico general,
Lenguaje I de Jone (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 con símbolos del alfabeto. El gráfico es el almacenamiento de la máquina . Cada nodo del gráfico tiene exactamente una flecha saliente etiquetada con cada símbolo, aunque algunas de ellas pueden volver al nodo original. Un nodo fijo del gráfico se identifica como el nodo de inicio o "activo".
Cada palabra de símbolos del alfabeto puede entonces traducirse a una ruta a través de la máquina; por ejemplo, 10011 se traduciría en tomar el borde 1 del nodo de inicio, luego el borde 0 del nodo resultante, luego el borde 0, luego el borde 1, luego el borde 1. De este modo, una palabra identifica un nodo, el nodo final de la ruta, pero esta identificación cambiará a medida que el gráfico cambie durante el cálculo.
La máquina puede recibir instrucciones que modifiquen la disposición del gráfico. Las instrucciones básicas son:
(1) instrucción new w , que crea un nuevo nodo al final de la ruta w , con todos sus bordes dirigidos al penúltimo nodo en w . (2) instrucción set w to v , que (re)dirige un borde a un nodo diferente. Aquí w y v representan palabras . La instrucción cambia el destino del último borde en la ruta w .
Algunos pasos en la ejecución de una máquina de 2 símbolos {0,1} con instrucciones: (1) new ε; (2) new 1; (3) new 11. La instrucción n.° 1 inicializa el gráfico de almacenamiento como un solo 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í, salta a la instrucción z; de lo contrario, continúa. Esta instrucción tiene el mismo propósito que el comando if en cualquier lenguaje de programación imperativo.
Evolución del grafo de almacenamiento en una máquina de 2 símbolos {0,1} con instrucciones: (1) nuevo ε; (2) nuevo 1; (3) nuevo 11; (4) nuevo 10; (5) establecer 111 en 10. En este momento, si la máquina hiciera si 10=111 entonces 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 solo lectura y a una cinta de salida de solo escritura, ambas conteniendo símbolos del alfabeto.
Modelo de máquina Kolmogorov-Uspenskii (máquina KU)
KUM difiere de SMM en que solo permite punteros invertibles: por 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 grafo de almacenamiento no está dirigido. Dado que los punteros salientes deben estar etiquetados con símbolos distintos del alfabeto, tanto los grafos 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 por 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 estados en lugar de una lista de instrucciones.
Consideraciones sobre el modelo de puntero-máquina
Uso del modelo en la teoría de la complejidad : van Emde Boas (1990) expresa su preocupación por el hecho de que esta forma de modelo abstracto es:
"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 en el que se sabe que esta medida subestima la verdadera complejidad del tiempo. La misma observación se aplica a la medida del espacio para la máquina" (van Emde Boas (1990) p. 35)
Gurevich también expresa preocupación:
"Pragmáticamente hablando, 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 la multiplicación de números 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 punteros paralelos (atomísticos); [9] también se utilizó un modelo de máquina de punteros paralelos de alto nivel (no atomístico) [10].
Máquina contadora : la máquina más primitiva, los conjuntos de instrucciones de los modelos básicos 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 secuenciales predeterminadas de manera similar a las máquinas contadoras básicas de 3 instrucciones.
Lectura adicional
La mayoría de las referencias y una bibliografía se encuentran en el artículo Máquina de registro . Las siguientes son específicas 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. En donde Ben-Amram describe los tipos y subtipos: (tipo 1a) Máquinas abstractas: modelos atomísticos que incluyen máquinas de Kolmogorov-Uspenskii (KUM), máquinas de modificación de almacenamiento de Schönhage (SMM), "autómata de enlace" de Knuth, APLM y AFLM (máquina atomística Pure-LISP) y (máquina atomística Full-LISP), máquinas de puntero atomísticas generales, lenguaje I de Jone; (tipo 1b) Máquinas abstractas: modelos de alto nivel, (tipo 2) Algoritmos de puntero.
Yuri Gurevich (2000), Sequential Abstract State Machines Capture Sequential Algorithms , ACM Transactions on Computational Logic, vol. 1, no. 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 modelos similares, como las "máquinas de acceso aleatorio", Gurevich hace referencia a:
John E. Savage (1998), Modelos de computación: explorando el poder de la computación. Addison Wesley Longman.
Yuri Gurevich (1988), On Kolmogorov Machines and Related Issues, la columna sobre "Lógica en la informática", Bulletin of European Association for Theoretical Computer Science, número 35, junio de 1988, 71-82. Introdujo la descripción unificada de las máquinas de Schönhage y Kolmogorov-Uspenskii que se utilizan aquí.
Arnold Schönhage (1980), Storage Modification Machines , Society for Industrial and Applied Mathematics, SIAM J. Comput. Vol. 9, No. 3, agosto de 1980. En este artículo, Schönhage muestra la equivalencia de su SMM con la "sucesora RAM" (Random Access Machine), etc. Hace referencia a un artículo anterior en el que presenta la 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 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).
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.
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 punteros"?, SIGACT News (Grupo de interés especial de la 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 , ACM Transactions on Computational Logic, 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 American Mathematical Society Translations, Serie II, Volumen 29 (1963), págs. 217-245.
^ Peter van Emde Boas , Modelos de máquinas y simulaciones , págs. 3–66, 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).
^ Gurevich (1988) p. 6 con referencia a Angluin D. y Valiant LG, "Algoritmos probabilísticos rápidos para circuitos y emparejamientos hamiltonianos", Journal of Computer and System Sciences 18 (1979) 155-193.
^ Yuri Gurevich (1988), Sobre las máquinas de Kolmogorov y cuestiones relacionadas, columna sobre "Lógica en Ciencias de la Computación", Boletín de la Asociación Europea de Ciencias de la Computación Teórica, Número 35, junio de 1988, 71-82.
^ Cook, Stephen A.; Dymond, Patrick W. (marzo de 1993). "Máquinas de puntero paralelo". Computational Complexity . 3 : 19–30. doi :10.1007/BF01200405.
^ Goodrich, MT; Kosaraju, SR (1996). "Ordenamiento en una máquina de puntero paralelo con aplicaciones para la evaluación de expresiones de conjuntos". Revista de la ACM . 43 (2): 331–361. doi :10.1145/226643.226670.
