En la informática teórica, una máquina puntero es un modelo de máquina computacional abstracto "atomista" similar a la máquina de acceso aleatorio . Un algoritmo de puntero es un algoritmo restringido al modelo de máquina de puntero. [1]
Dependiendo del tipo, una máquina de puntero puede denominarse autómata de enlace, máquina KU, SMM, máquina LISP atomística, máquina de puntero de árbol, etc. (cf Ben-Amram 1995). Existen al menos tres variedades principales en la literatura: el modelo Kolmogorov-Uspenskii (KUM, KU-machine), el autómata de enlace Knuth y el modelo Schönhage Storage Modification Machine (SMM). El SMM parece ser el más común.
Desde su "cinta de solo lectura" (o equivalente), una máquina de puntero recibe entradas —secuencias de símbolos delimitadas ("palabras") compuestas por al menos dos símbolos, por ejemplo, {0, 1} - y escribe secuencias de símbolos de salida en un salida de cinta "sólo de escritura" (o equivalente). Para transformar una secuencia de símbolos (palabra de entrada) en una secuencia de símbolos de salida, la máquina está equipada con un "programa", una máquina de estado finito (memoria y lista de instrucciones). A través de su máquina de estado, el programa lee los símbolos de entrada, opera en su estructura de almacenamiento, una colección de "nodos" (registros) interconectados por "bordes" (punteros etiquetados con los símbolos, por ejemplo, {0, 1}) y escribe símbolos en el cinta de salida.
Las máquinas de puntero no pueden hacer aritmética. La computación procede sólo 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. La "información" está en la estructura de almacenamiento .
Tipos de "máquinas de puntero"
Tanto Gurevich como Ben-Amram enumeran varios modelos "atomísticos" muy similares de "máquinas abstractas"; Ben-Amram cree que los 6 "modelos atomísticos" deben distinguirse de los modelos de "alto nivel". Este artículo discutirá los siguientes 3 modelos atomísticos en particular:
- Máquinas de modificación de almacenamiento de Schönhage (SMM),
- Máquinas Kolmogorov – Uspenskii (KUM o KU-Machines),
- El "autómata de enlace" de Knuth
Pero Ben-Amram agrega más:
- Máquina atomística pura-LISP (APLM)
- Máquina atomista full-LISP (AFLM),
- Máquinas de puntero atomístico general,
- Idioma de Jone I (dos tipos)
Problemas con el modelo de puntero-máquina
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 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 1988 también expresa preocupación:
- "Hablando pragmáticamente, el modelo de Schönhage proporciona una buena medida de complejidad temporal en el estado actual de la técnica (aunque preferiría algo similar a las computadoras de acceso aleatorio de Angluin y Valiant)" (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.)
El hecho de que, en §3 y §4 (págs. 494-497), el propio Schönhage (1980) demuestre las equivalencias en tiempo real de sus dos modelos de máquina de acceso aleatorio "RAM0" y "RAM1" lleva a uno a cuestionar la necesidad del SMM para estudios de complejidad.
Usos potenciales del modelo : Sin embargo, Schönhage (1980) demuestra en su §6, Multiplicación de enteros en tiempo lineal . Y Gurevich se pregunta si la "máquina KU paralela" "se parece un poco al cerebro humano" (Gurevich (1988) p. 5).
Modelo de máquina de modificación de almacenamiento (SMM) de Schönhage
El modelo SMM de Schönhage parece ser el más común y aceptado. Es bastante diferente al modelo de máquina registradora y otros modelos computacionales comunes, por ejemplo, la máquina de Turing basada en cinta o los agujeros etiquetados y guijarros indistinguibles de la máquina contador . [2]
La computadora consta de un alfabeto fijo de símbolos de entrada y un gráfico dirigido mutable (también conocido como diagrama de estado ) con sus flechas etiquetadas con símbolos del alfabeto. Cada nodo del gráfico tiene exactamente una flecha de salida etiquetada con cada símbolo, aunque algunos de estos pueden volver al nodo original. Un nodo fijo del gráfico se identifica como el nodo inicial o "activo".
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 la ruta 1 desde el nodo de inicio, luego la ruta 0 desde el nodo resultante, luego la ruta 0, luego la ruta 1, luego la ruta 1. La ruta puede, a su vez, identificarse con el nodo resultante, 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 la nueva w instrucción, lo que crea un nuevo nodo que es el "resultado" de seguir la cadena w , y el conjunto w a v instrucción que (re) dirige una ventaja a un nodo diferente. Aquí w y v representan palabras . v es una palabra anterior , es decir, una cadena de símbolos creada previamente, de modo que el borde redirigido apuntará "hacia atrás" a un nodo antiguo que es el "resultado" de esa cadena.
(1) new w : crea un nuevo nodo. w representa la nueva palabra que crea el nuevo nodo. La máquina lee la palabra w , siguiendo la ruta representada por los símbolos de w hasta que la máquina llega al último símbolo "adicional" de la palabra. En cambio, el símbolo adicional fuerza al último estado a crear un nuevo nodo y "voltear" su flecha correspondiente (la etiquetada con ese símbolo) desde su posición anterior para apuntar al nuevo nodo. El nuevo nodo, a su vez, apunta todos sus bordes hacia el antiguo último estado, donde simplemente "descansan" hasta que otro nuevo o conjunto los redirige . En cierto sentido, los nuevos nodos están "durmiendo", esperando una asignación. En el caso del nodo inicial o central, igualmente comenzaríamos con sus dos bordes apuntando hacia sí mismo.
- Ejemplo: Sea "w" 10110 [1], donde el carácter final está entre paréntesis para indicar su estado especial. Tomamos el borde 1 del nodo alcanzado por 10110 (al final de un camino de cinco bordes, por lo tanto, de seis nodos), y lo apuntamos a un nuevo séptimo nodo. Los dos bordes de este nuevo nodo apuntan "hacia atrás" al sexto nodo de la ruta.
(2) Set w a v : redirecciones (mueve) un borde (flecha) de la trayectoria representada por la palabra w a un antiguo nodo que representa la palabra v . Nuevamente, es la última flecha en la ruta la que se redirige.
- Ejemplo: Establecer 1011011 en 1011 , después de la instrucción anterior, cambiaría la flecha 1 del nuevo nodo en 101101 para apuntar al quinto nodo en la ruta, alcanzado en 1011. Por lo tanto, la ruta 1011011 ahora tendría el mismo resultado que 1011.
(3) Si v = w entonces la instrucción z : instrucción condicional que compara dos trayectorias representadas por palabras w y v para ver si terminan al 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 su contraparte en una máquina de registro o máquina Wang b , correspondiente a la capacidad de una máquina de Turing para saltar a un nuevo estado.
Modelo de "autómata de enlace" de Knuth
Según Schoenhage, Knuth señaló que el modelo SMM coincide con un tipo especial de "autómatas de enlace" explicados brevemente en el volumen uno de El arte de la programación informática (cf. [4, págs. 462-463]).
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. Dado que los punteros salientes deben estar etiquetados con distintos símbolos del alfabeto, tanto los gráficos KUM como los SMM tienen un grado externo 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 oposición al puramente informativo), como los de la cita anterior de van Emde Boas.
Una diferencia adicional es que el KUM fue pensado como una generalización de la máquina de Turing, por lo que permite que el nodo "activo" en ese momento se mueva alrededor del gráfico. En consecuencia, los nodos se pueden especificar mediante caracteres individuales en lugar de palabras, y la acción a realizar se puede determinar mediante una tabla de estado en lugar de una lista fija de instrucciones.
Ver también
Máquina de registro: modelo computacional de máquina abstracta basada en registros genéricos
- 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 contadora con capacidad de direccionamiento indirecto adicional
- Máquina de programa almacenado de acceso aleatorio —RASP: máquina basada en contador o basada en RAM con un "programa de instrucciones" que se encuentra en los propios registros en la materia de una máquina Universal de Turing, es decir, la arquitectura von Neumann .
Máquina de Turing: modelo computacional genérico de máquina abstracta basada en cinta
- Máquina de Post-Turing —Máquina minimalista de una cinta, dos direcciones, 1 símbolo {espacio en blanco, marca} similar a la de Turing pero con ejecución de instrucciones secuenciales por defecto de una manera similar a las máquinas contadoras básicas de 3 instrucciones.
Referencias
- ^ Cloteaux, Brian; Ranjan, Desh (2006). "Algunos resultados de separación entre clases de algoritmos de puntero" .
- ↑ El tratamiento es el de van Emde Boas 1990 más que el de Schönhage, que carece de ejemplos.
La mayoría de las referencias y una bibliografía se encuentran en la máquina de registro de artículos . Los siguientes son específicos de este artículo:
- Amir Ben-Amram (1995), ¿Qué es una "máquina de puntero"? , SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory) ", volumen 26, 1995. también: DIKU, Departamento de Ciencias de la Computación, Universidad de Copenhague, [email protected]. Donde Ben-Amram describe los tipos y subtipos: (tipo 1a) Máquinas abstractas: modelos atomistas que incluyen máquinas Kolmogorov-Uspenskii (KUM), máquinas de modificación de almacenamiento de Schönhage (SMM), "Linking Automaton" de Knuth, APLM y AFLM (máquina Atomistic Pure-LISP) y (Atomistic Full LISP machine), Máquinas de puntero atomistas generales, Lenguaje I de Jone; (tipo 1b) Máquinas abstractas: Modelos de alto nivel, (tipo 2) Algoritmos de puntero.
- 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.
- Yuri Gurevich (2000), Máquinas de estado abstracto secuencial capturan algoritmos secuenciales , Transacciones ACM en lógica computacional, 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 obtener más información sobre modelos similares, como "máquinas de acceso aleatorio", Gurevich hace referencia:
- John E. Savage (1998), Modelos de computación: exploración del poder de la computación . Addison Wesley Longman.
- Yuri Gurevich (1988), On Kolmogorov Machines and Related Issues , la 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. Introdujo la descripción unificada de las máquinas 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. Bibliogr. Institut, Mannheim, 1970, págs. 69–383.
- Peter van Emde Boas , Machine Models and Simulations págs. 3-66, que aparece en:
- Jan van Leeuwen , ed. "Manual de Ciencias de la Computación Teóricas. Volumen A: Algoritmos y Complejidad , The MIT PRESS / Elsevier, 1990. ISBN 0-444-88071-2 (volumen A). QA 76.H279 1990.
- El tratamiento de van Emde Boas de los SMM aparece en las págs. 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 eficaz.