Máquina de punteros

En informática teórica , una máquina de punteros es una máquina computacional abstracta atomística cuya estructura de almacenamiento es un grafo . Un algoritmo de punteros también podría ser un algoritmo restringido al modelo de máquina de punteros. ^{[ 1 ]}

Algunos tipos particulares de máquinas de punteros se denominan autómata de enlace, máquina KU, SMM, máquina LISP atomística , máquina de punteros 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, modificándolos y realizando diversas pruebas en su estructura de almacenamiento (el patrón de nodos y punteros), y generando símbolos de salida según los resultados de dichas pruebas. En este sentido, el modelo es similar a la máquina de Turing .

Tanto Gurevich como Ben-Amram enumeran varios modelos "atomísticos" muy similares de "máquinas abstractas"; ^{[ 3 ] [ 2 ]} Ben-Amram cree que los "modelos atomísticos" deben distinguirse de los modelos de "alto nivel". A continuación se presentan 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 tratan con mayor detalle en este artículo:

• Máquina atomística puramente LISP (APLM)
• Máquina atomística completa LISP (AFLM),
• Máquinas de punteros atomísticos generales,
• El lenguaje de Jones (dos tipos).

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 grafo dirigido mutable cuyas flechas están etiquetadas con símbolos del alfabeto. El grafo es el sistema de almacenamiento de la máquina . Cada nodo del grafo tiene exactamente una flecha saliente etiquetada con cada símbolo, aunque algunas de estas pueden regresar al nodo original. Un nodo fijo del grafo se identifica como el nodo de inicio o "activo".

Cada palabra de símbolos del alfabeto se puede traducir a una ruta a través de la máquina; por ejemplo, 10011 se traduciría en tomar la arista 1 desde el nodo inicial, luego la arista 0 desde el nodo resultante, luego la arista 0, luego la arista 1, luego la arista 1. De esta manera, una palabra identifica un nodo, el nodo final de la ruta, pero esta identificación cambiará a medida que el grafo cambie durante el cálculo.

La máquina puede recibir instrucciones que modifican la disposición del gráfico. Las instrucciones básicas son:

(1) nueva instrucción w , que crea un nuevo nodo al final del camino w , con todos sus bordes dirigidos al penúltimo nodo en w .

(2) instrucción de establecer w a v que (re)dirige una arista a un nodo diferente. Aquí w y v representan palabras . La instrucción da como resultado cambiar el destino de la última arista en la ruta w .

(3) Si v = w, entonces instrucción z  : Instrucción condicional que compara dos rutas representadas 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 cumple la misma función que el comando if en cualquier lenguaje de programación imperativo .

(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.

Knuth señaló que el modelo SMM coincide con un tipo de "autómata de enlace" explicado brevemente en el primer volumen de El arte de la programación informática . ^{[ 4 ]}

KUM se diferencia de SMM en que solo permite punteros invertibles: por cada puntero de un nodo x a un nodo y, debe existir 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 de O(1). Sin embargo, la invertibilidad de los punteros KUM también restringe el grado de entrada a O(1). Esto resuelve algunas preocupaciones relacionadas con el realismo físico (en contraposición al realismo puramente informacional).

Existen otras diferencias menores entre los modelos, como la forma del programa: una tabla de estados en lugar de una lista de instrucciones.

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 de tiempo se basa en un tiempo uniforme en un contexto donde se sabe que esta medida subestima la verdadera complejidad temporal. La misma observación se aplica a la medida de espacio para la máquina" (van Emde Boas (1990), p. 35).

Gurevich también expresa su preocupación:

"En términos prácticos, el modelo de Schönhage proporciona una buena medida de la complejidad temporal en el estado actual de la técnica (aunque yo preferiría algo similar 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 la SMM. ^{[ 4 ]}

Algoritmos en el modelo SMM : Schönhage demuestra que el SMM puede realizar multiplicaciones enteras en tiempo lineal. ^{[ 4 ]}

Usos potenciales del modelo : Gurevich se pregunta si una máquina KU paralela "se asemeja de alguna manera 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 paralelo (atomista); ^{[ 9 ]} también se ha utilizado un modelo de máquina de punteros paralelo de alto nivel (no atomista) ^{[ 10 ].}

Máquina de registros: modelo computacional de máquina abstracta genérica basada en registros

• 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 registradoras.
• Máquina de acceso aleatorio (RAM): máquina de contador con capacidad de direccionamiento indirecto añadida.
• Máquina de programa almacenado de acceso aleatorio (RASP): máquina basada en contador o en RAM con un "programa de instrucciones" que se encuentra en los propios registros, al estilo de una máquina de Turing universal , es decir, la arquitectura de von Neumann .

Máquina de Turing: modelo computacional de máquina abstracta genérica basada en cinta.

• Máquina post-Turing : una máquina minimalista de una cinta, dos direcciones, 1 símbolo {en blanco, marca} similar a Turing, pero con ejecución de instrucciones secuencial por defecto de una manera similar a las máquinas básicas de contador de 3 instrucciones.

La mayoría de las referencias y la bibliografía se encuentran en el artículo " Máquina de registro" . Lo siguiente es específico de este artículo:

• Amir Ben-Amram (1995), ¿Qué es una "máquina de punteros"?, SIGACT News (ACM Special Interest Group on Automata and Computability Theory)", volumen 26, 1995. En el que 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 punteros atomísticas generales, lenguaje I de Jones; (tipo 1b) Máquinas abstractas: modelos de alto nivel, (tipo 2) algoritmos de punteros.
• Yuri Gurevich (2000), Sequential Abstract State Machines Capture Sequential Algorithms , ACM Transactions on Computational Logic, vol. 1, n.º 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 punteros" de Knuth. Para más información, Gurevich hace referencia a modelos similares como las "máquinas de acceso aleatorio":
  • John E. Savage (1998), Modelos de computación: Explorando el 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 la informática", Boletín de la Asociación Europea de Informática Teórica, 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 utiliza 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 el que Schönhage muestra la equivalencia de su SMM con la "RAM sucesora" (Random Access Machine), etc. Se refiere a un artículo anterior donde introduce 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 y simulaciones de máquinas, págs.  3-66, publicado 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 análisis de van Emde Boas sobre los SMM aparece en las páginas 32-35. Este análisis aclara el trabajo de Schönhage (1980); lo sigue de cerca, pero lo amplía ligeramente. Ambas referencias pueden ser necesarias para una comprensión efectiva.