Máquina de Turing de solo lectura

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 comportan como una máquina de Turing estándar y pueden moverse en ambas direcciones a través de la entrada, excepto que no pueden escribir en su cinta de entrada. La máquina en su forma básica es equivalente a un autómata finito determinista en potencia computacional y, por lo tanto, solo puede analizar un lenguaje regular .

Definimos una máquina de Turing estándar por la tupla de 9

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

• ${\estilo de visualización Q}$es un conjunto finito de estados ;
• ${\estilo de visualización \Sigma}$es el conjunto finito del alfabeto de entrada ;
• ${\estilo de visualización \Gamma}$es el alfabeto de cinta finita ;
• ${\displaystyle \vdash \en \Gamma -\Sigma }$es el marcador final izquierdo ;
• ${\displaystyle \_\en \Gamma -\Sigma }$es el símbolo en blanco ;
• ${\displaystyle \delta :Q\veces \Gamma \rightarrow Q\veces \Gamma \veces \{L,R\}}$es la función de transición ;
• ${\displaystyle s\en Q}$es el estado inicial ;
• ${\displaystyle t\en Q}$es el estado de aceptación ;
• ${\displaystyle r\en Q,~r\neq t}$es el estado de rechazo .

Entonces, dado el estado inicial de lectura del símbolo , tenemos una transición definida por que reemplaza con , pasa al estado y mueve el "cabezal de lectura" en dirección (izquierda o derecha) para leer la siguiente entrada. ^[1] Sin embargo, en nuestra máquina de solo lectura 2DFA, siempre. ${\estilo de visualización q}$${\estilo de visualización a}$${\displaystyle \delta(q,a)=(q_{2},a_{2},d)}$${\estilo de visualización a}$$estilo de visualización a_{2}$$estilo de visualización q_{2}}$${\estilo de visualización d}$$estilo de visualización a=a_{2}$

Este modelo es ahora equivalente a un DFA. La prueba implica construir una tabla que enumere el resultado de retroceder con el control en cualquier estado dado; al comienzo del cálculo, este es simplemente el resultado de intentar pasar el 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 una cantidad fija de estados, y hay una cantidad fija de estados en el alfabeto de cinta, la tabla tiene un tamaño fijo y, por lo tanto, se puede calcular mediante otra máquina de estados finitos. Esta máquina, sin embargo, nunca necesitará retroceder y, por lo tanto, es un DFA.

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 darse a múltiples estados dada la misma entrada) es reducible a un DFA.

Otras variantes de este modelo permiten una mayor complejidad computacional . Con una única 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 ⁿ b ⁿ c ⁿ } puede analizarse mediante un algoritmo que verifica primero que haya el mismo número de a y b, luego rebobina y verifica que haya el mismo número de b y c. Con la ayuda adicional del no determinismo , la máquina puede analizar cualquier lenguaje libre de 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 múltiples cabezales de cinta, puede analizar cualquier lenguaje en L o NL , dependiendo de si se permite el no determinismo. ^[3]

En la definición de una máquina de Turing universal se utiliza una máquina de Turing de solo lectura para aceptar la definición de la máquina de Turing que se va a modelar, después de lo cual el cálculo continúa con una máquina de Turing estándar.

En la investigación moderna, el modelo ha adquirido importancia para describir una nueva clase de complejidad de autómatas finitos cuánticos o autómatas probabilísticos deterministas . ^{[4] [5]}

• Computabilidad
• Equivalentes de la máquina de Turing
• Máquina apiladora
• Autómata de cola
• Computadora cuántica

• Conferencia sobre autómatas de estados finitos por Adam Webber