Autómata de cola

Modelo computacional, equivalente a las máquinas de Turing

Una máquina de cola , autómata de cola o autómata pullup (PUA) ^{[ cita requerida ]} es una máquina de estados finitos con la capacidad de almacenar y recuperar datos de una cola de memoria infinita . Su diseño es similar a un autómata pushdown pero se diferencia al reemplazar la pila con esta cola. Una máquina de cola es un modelo de computación equivalente a una máquina de Turing y, por lo tanto, puede procesar la misma clase de lenguajes formales .

Teoría

Una máquina de cola se puede definir como una sextupla

${\displaystyle M=(Q,\Sigma ,\Gamma ,\$,s,\delta )}$dónde

• ${\displaystyle \,Q}$es un conjunto finito de estados ;
• ${\displaystyle \,\Sigma \subset \Gamma }$es el conjunto finito del alfabeto de entrada ;
• ${\displaystyle \,\Gamma }$es el alfabeto de cola finita ;
• ${\displaystyle \,\$\in \Gamma \setminus \Sigma }$es el símbolo de la cola inicial ;
• ${\displaystyle \,s\in Q}$es el estado inicial ;
• ${\displaystyle \,\delta :Q\times \Gamma \rightarrow Q\times \Gamma ^{*}}$es la función de transición .

Una configuración de máquina es un par ordenado de su estado y el contenido de la cola , donde denota el cierre de Kleene de . La configuración inicial en una cadena de entrada se define como , y la transición de una configuración a la siguiente se define como: ${\displaystyle \,(q,\gamma )\in Q\times \Gamma ^{*}}$ ${\displaystyle \,\Gamma ^{*}}$ ${\displaystyle \,\Gamma }$ ${\displaystyle \,x}$ ${\displaystyle \,(s,x\$)}$ ${\displaystyle \rightarrow _{M}^{1}}$

${\displaystyle \,(p,A\alpha )\rightarrow _{M}^{1}(q,\alpha \gamma )}$

donde es un símbolo del alfabeto de colas, es una secuencia de símbolos de cola ( ), y . Observe la propiedad "primero en entrar, primero en salir" de la cola en la relación. ${\displaystyle A}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha \in \Gamma ^{*}}$ ${\displaystyle (q,\gamma )=\delta (p,A)}$

La máquina acepta una cadena si después de un número finito de transiciones la configuración inicial evoluciona hasta agotar la cadena (alcanzando la cadena nula ), o dicho de otro modo, si ^[1] ${\displaystyle \,x\in \Sigma ^{*}}$ ${\displaystyle \,\epsilon }$ ${\displaystyle \,(s,x\$)\rightarrow _{M}^{*}(q,\epsilon ).}$

Completitud de Turing

Podemos demostrar que una máquina de cola es equivalente a una máquina de Turing mostrando que una máquina de cola puede simular una máquina de Turing y viceversa.

Una máquina de Turing puede ser simulada por una máquina de cola que mantiene una copia del contenido de la máquina de Turing en su cola en todo momento, con dos marcadores especiales: uno para la posición de la cabeza de la máquina de Turing y otro para el final de la cinta; sus transiciones simulan las de la máquina de Turing al recorrer toda la cola, sacando cada uno de sus símbolos y volviendo a poner en cola el símbolo sacado o, cerca de la posición de la cabeza, el equivalente del efecto de transición de la máquina de Turing.

Una máquina de cola puede simularse mediante una máquina de Turing, pero es más fácil hacerlo mediante una máquina de Turing de múltiples cintas , que se sabe que es equivalente a una máquina de una sola cinta normal. La máquina de cola que simula lee la entrada en una cinta y almacena la cola en la segunda, con entradas y salidas definidas por transiciones simples a los símbolos de inicio y fin de la cinta. ^[2] Una prueba formal de esto es a menudo un ejercicio en los cursos teóricos de informática.

Aplicaciones

Las máquinas de cola ofrecen un modelo simple en el que basar arquitecturas informáticas , ^{[3] [4]} lenguajes de programación o algoritmos . ^{[5] [6]}

Véase también

• Computabilidad
• Equivalentes de la máquina de Turing
• Autómata finito determinista
• Sistema de etiquetas
• Manufactoria, un juego flash de navegador que desafía al jugador a implementar varios algoritmos utilizando un modelo de máquina de cola.

Referencias

1. Kozen, Dexter C. (1997) [1951]. David Gries, Fred B. Schneider (ed.). Automata and Computability (tapa dura). Undergraduate Texts in Computer Science (1.ª ed.). Nueva York: Springer-Verlag. págs. 368–370. ISBN 978-0-387-94907-9.
2. Rus, Teodor. "Variantes de las máquinas de Turing" (PDF) . Apuntes de clase sobre teoría de la computación . Universidad de Iowa , Iowa City, IA, 52242-1419. Archivado desde el original (PDF) el 21 de septiembre de 2008. Consultado el 6 de noviembre de 2007 .
3. Feller, M.; MD Ercegovac (1981). "Máquinas de cola: una organización para computación paralela". Conpar 81. Apuntes de clase en informática. Vol. 111. págs. 37–47. doi :10.1007/BFb0105108. ISBN. 978-3-540-10827-6.
4. Schmit, H.; Levine, B.; Ylvisaker, B. (2002). "Máquinas de cola: compilación de hardware en hardware". Actas. 10.º Simposio anual IEEE sobre máquinas informáticas personalizadas programables en campo . pp. 152–160. CiteSeerX 10.1.1.6.7718 . doi :10.1109/FPGA.2002.1106670. ISBN .  978-0-7695-1801-5.S2CID8993845  .​
5. Moore, Christopher (20 de septiembre de 1999). "Colas, pilas y trascendentalidad en la transición al caos". Seminario del Proyecto Algoritmos . INRIA . Consultado el 6 de noviembre de 2007 .
6. von Thun, Manfred (2007). "Una máquina de colas para evaluar expresiones". Universidad La Trobe . Archivado desde el original el 2007-08-07 . Consultado el 2007-11-06 .