Pointer machine

In theoretical computer science, a pointer machine is an atomistic abstract computational machine whose storage structure is a graph. A pointer algorithm could also be an algorithm restricted to the pointer machine model.^[1]

Some particular types of pointer machines are called a linking automaton, a KU-machine, an SMM, an atomistic LISP machine, a tree-pointer machine, etc.^[2]

Pointer machines do not have arithmetic instructions. Computation proceeds only by reading input symbols, modifying and doing various tests on its storage structure—the pattern of nodes and pointers, and outputting symbols based on the tests. In this sense, the model is similar to the Turing machine.

Both Gurevich and Ben-Amram list a number of very similar "atomistic" models of "abstract machines";^[3][2] Ben-Amram believes that the "atomistic models" must be distinguished from "high-level" models. The following atomistic models will be presented below:

• Schönhage's storage modification machines (SMM),^[4]
• Kolmogorov–Uspenskii machines (KUM or KU-Machines).^[5]

Ben-Amram also presents the following varieties, not further discussed in this article:

• Atomistic pure-LISP machine (APLM)
• Atomistic full-LISP machine (AFLM),
• General atomistic pointer machines,
• Jone's I language (two types).

The following presentation follows van Emde Boas.^[6]

The machine consists of a fixed alphabet of input symbols, a fixed program, and a mutable directed graph with its arrows labelled by alphabet symbols. The graph is the machine's storage. Each node of the graph has exactly one outgoing arrow labelled with each symbol, although some of these may loop back into the original node. One fixed node of the graph is identified as the start or "active" node.

Each word of symbols in the alphabet can then be translated to a pathway through the machine; for example, 10011 would translate to taking edge 1 from the start node, then edge 0 from the resulting node, then edge 0, then edge 1, then edge 1. Thus a word identifies a node, the final node of the path, but this identification will change as the graph changes during the computation.

The machine can receive instructions which change the layout of the graph. The basic instructions are:

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