Una máquina de cola o un autómata de cola es una máquina de estado finito con la capacidad de almacenar y recuperar datos de una cola de memoria infinita . 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 tupla de seis
- dónde
- es un conjunto finito de estados ;
- es el conjunto finito del alfabeto de entrada ;
- es el alfabeto de cola finito ;
- es el símbolo de la cola inicial ;
- es el estado de inicio ;
- es la función de transición .
Una configuración de máquina es un par ordenado de su estado y contenido de la cola, dónde 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:
dónde es un símbolo del alfabeto de la cola, es una secuencia de símbolos de cola (), y . Tenga en cuenta la propiedad "primero en entrar, primero en salir" de la cola en la relación.
La máquina acepta una cuerda si después de un número finito de transiciones la configuración inicial evoluciona para agotar la cadena (alcanzando una cadena nula ), o [1]
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 del TM y otro para el final de la cinta; sus transiciones simulan las de la MT recorriendo toda la cola, quitando cada uno de sus símbolos y volviendo a colocar el símbolo reventado o, cerca de la posición de la cabeza, el equivalente del efecto de transición de la MT.
Una máquina de cola puede ser simulada por una máquina de Turing, pero más fácilmente por una máquina de Turing de cintas múltiples , que se sabe que es equivalente a una máquina normal de una sola cinta. La máquina de simulación de cola lee la entrada en una cinta y almacena la cola en la segunda, con pulsaciones y estallidos definidos por transiciones simples a los símbolos de inicio y finalización de la cinta. [2] Una prueba formal de esto es a menudo un ejercicio en cursos de informática teórica.
Aplicaciones
Las máquinas de cola ofrecen un modelo simple en el que basar arquitecturas de computadora , [3] [4] lenguajes de programación o algoritmos . [5] [6]
Ver también
- Computabilidad
- Equivalentes de la máquina de Turing
- Autómata finito determinista
- Autómata de empuje
- Sistema de etiquetas
- Manufactoria , un juego flash de navegador que le asigna al jugador la tarea de implementar varios algoritmos utilizando un modelo de máquina de cola.
Referencias
- ^ Kozen, Dexter C. (1997) [1951]. David Gries, Fred B. Schneider (ed.). Autómatas y computabilidad (tapa dura). Textos de Licenciatura en Informática (1 ed.). Nueva York: Springer-Verlag. págs. 368 –370. ISBN 978-0-387-94907-9.
- ^ Rus, Teodor. "Variantes de las máquinas de Turing" (PDF) . Notas de clase que cubren la 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 .
- ^ Feller, M .; MD Ercegovac (1981). Máquinas de cola: una organización para el cálculo paralelo . Apuntes de conferencias en informática . 111 . págs. 37–47. doi : 10.1007 / BFb0105108 . ISBN 978-3-540-10827-6.
- ^ Schmit, H .; Levine, B .; Ylvisaker, B. (2002). "Máquinas de cola: compilación de hardware en hardware". Actas. Décimo Simposio Anual de IEEE sobre Máquinas de Computación Personalizadas Programables en Campo . págs. 152–160. CiteSeerX 10.1.1.6.7718 . doi : 10.1109 / FPGA.2002.1106670 . ISBN 978-0-7695-1801-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 .
- ^ von Thum, Manfred (2007). "Una máquina de cola para evaluar expresiones" . Universidad LaTrobe. Archivado desde el original el 7 de agosto de 2007 . Consultado el 6 de noviembre de 2007 .