Introducción a la máquina de Turing
Una máquina de Turing es un dispositivo de aceptación que acepta los idiomas (conjunto enumerable recursivamente) generados por gramáticas de tipo 0. Fue inventado en 1936 por Alan Turing.
Definición
Una máquina de Turing (TM) es un modelo matemático que consiste en una cinta de longitud infinita dividida en celdas en las que se da entrada. Consiste en un cabezal que lee la cinta de entrada. Un registro estatal almacena el estado de la máquina de Turing. Después de leer un símbolo de entrada, se reemplaza con otro símbolo, se cambia su estado interno y se mueve de una celda a la derecha o izquierda. Si la TM alcanza el estado final, se acepta la cadena de entrada; de lo contrario, se rechaza.
Una TM se puede describir formalmente como una tupla de 7 (Q, X, ∑, δ, q 0 , B, F) donde -
Q es un conjunto finito de estados
X es el alfabeto de la cinta
∑ es el alfabeto de entrada
δes una función de transición; δ: Q × X → Q × X × {Left_shift, Right_shift}.
q0 es el estado inicial
B es el símbolo en blanco
F es el conjunto de estados finales
Comparación con el autómata anterior
La siguiente tabla muestra una comparación de cómo una máquina de Turing se diferencia de Finite Automaton y Pushdown Automaton.
| Máquina | Estructura de datos de pila | Determinista? |
|---|---|---|
| Autómata finito | N / A | si |
| Autómata de empuje | Último en entrar, primero en salir (LIFO) | No |
| Máquina de Turing | Cinta infinita | si |
Ejemplo de máquina de Turing
Máquina de Turing M = (Q, X, ∑, δ, q 0 , B, F) con
- Q = {q 0 , q 1 , q 2 , q f }
- X = {a, b}
- ∑ = {1}
- q 0 = {q 0 }
- B = símbolo en blanco
- F = {q f }
δ está dado por -
| Símbolo del alfabeto de cinta | Estado actual 'q 0 ' | Estado actual 'q 1 ' | Estado actual 'q 2 ' |
|---|---|---|---|
| una | 1Rq 1 | 1Lq 0 | 1Lq f |
| segundo | 1Lq 2 | 1Rq 1 | 1Rq f |
Aquí la transición 1Rq 1 implica que el símbolo de escritura es 1, la cinta se mueve hacia la derecha y el siguiente estado es q 1 . De manera similar, la transición 1Lq 2 implica que el símbolo de escritura es 1, la cinta se mueve hacia la izquierda y el siguiente estado es q 2 .
Complejidad temporal y espacial de una máquina de Turing
Para una máquina de Turing, la complejidad del tiempo se refiere a la medida del número de veces que se mueve la cinta cuando la máquina se inicializa para algunos símbolos de entrada y la complejidad del espacio es el número de celdas de la cinta escritas.
Complejidad temporal todas las funciones razonables -
T(n) = O(n log n)
Complejidad espacial de TM -
S(n) = O(n)