Una máquina de Turing de solo lectura o un autómata de estado finito determinista bidireccional (2DFA) es una clase de modelos de computabilidad que se comporta como una máquina de Turing estándar y puede moverse en ambas direcciones a través de la entrada, excepto que no puede escribir en su cinta de entrada. La máquina en su forma desnuda es equivalente a un autómata finito determinista en potencia computacional y, por lo tanto, solo puede analizar un lenguaje regular .
Teoría
Definimos una máquina de Turing estándar por la tupla de 9
dónde
- es un conjunto finito de estados ;
- es el conjunto finito del alfabeto de entrada ;
- es el alfabeto de cinta finito ;
- es el marcador final izquierdo ;
- es el símbolo en blanco ;
- es la función de transición ;
- es el estado de inicio ;
- es el estado de aceptación ;
- es el estado de rechazo .
Así que dado el estado inicial símbolo de lectura , tenemos una transición definida por que reemplaza con , transiciones al estado y mueve el "cabezal de lectura" en la dirección (izquierda o derecha) para leer la siguiente entrada. [1] Sin embargo, en nuestra máquina de solo lectura 2DFA, siempre.
Este modelo ahora es equivalente a un DFA. La prueba implica la construcción de una tabla que enumera el resultado de retroceder con el control en cualquier estado dado; al comienzo del cálculo, esto es simplemente el resultado de intentar pasar del marcador final izquierdo en ese estado. En cada movimiento hacia la derecha, la tabla se puede actualizar utilizando los valores de la tabla anterior y el carácter que estaba en la celda anterior. Dado que el control de cabeza original tenía un número fijo de estados, y hay un número fijo de estados en el alfabeto de la cinta, la tabla tiene un tamaño fijo y, por lo tanto, puede ser calculada por otra máquina de estados finitos. Sin embargo, esta máquina nunca necesitará retroceder y, por lo tanto, es un DFA.
Variantes
Varias variantes de este modelo también son equivalentes a los DFA. En particular, el caso no determinista (en el que la transición de un estado puede ser a varios estados con la misma entrada) es reducible a un DFA.
Otras variantes de este modelo permiten una mayor complejidad computacional . Con una sola pila infinita, el modelo puede analizar (al menos) cualquier lenguaje que sea computable por una máquina de Turing en tiempo lineal . [2] En particular, el lenguaje {a n b n c n } puede ser analizado por un algoritmo que verifica primero que hay el mismo número de a y b, luego rebobina y verifica que hay el mismo número de b y c . Con la ayuda adicional del no determinismo, la máquina puede analizar cualquier lenguaje sin contexto . Con dos pilas infinitas, la máquina es equivalente a Turing y puede analizar cualquier lenguaje formal recursivo .
Si se permite que la máquina tenga varios cabezales de cinta, puede analizar cualquier idioma en L o NL , según se permita el no determinismo. [3]
Aplicaciones
Una máquina de Turing de solo lectura se utiliza en la definición de una máquina de Turing universal para aceptar la definición de la máquina de Turing que se va a modelar, después de lo cual continúa el cálculo con una máquina de Turing estándar.
En la investigación moderna, el modelo se ha vuelto importante para describir una nueva clase de complejidad de autómatas finitos cuánticos o autómatas probabilísticos deterministas . [4] [5]
Ver también
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. 158 , 210, 224. ISBN 978-0-387-94907-9.
- ^ Complejidad computacional de Wagner y Wechsung, sección 13.3 (1986, ISBN 90-277-2146-7 )
- ^ Complejidad computacional de Wagner y Wechsung, sección 13.1 (1986, ISBN 90-277-2146-7 )
- ^ Kondacs, A .; J. Watrous (1997). Sobre el poder de los autómatas cuánticos de estado finito . 38º Simposio Anual sobre Fundamentos de la Informática (FOCS '97) . págs. 66–75. CiteSeerX 10.1.1.49.6392 . doi : 10.1109 / SFCS.1997.646094 . ISBN 978-0-8186-8197-4. Archivado desde el original (- Búsqueda académica ) el 23 de agosto de 2007 . Consultado el 7 de noviembre de 2007 .
- ^ Dwork, Cynthia ; Stockmeyer, Larry (1990). "Una brecha de complejidad de tiempo para autómatas probabilísticos de estado finito de 2 vías" . Revista SIAM de Computación . 19 (6): 1011–1023. doi : 10.1137 / 0219069 . Archivado desde el original el 25 de octubre de 2009 . Consultado el 7 de noviembre de 2007 .