Introducción a la máquina de Turing

Una máquina de Turing es un dispositivo de aceptación que acepta los lenguajes (conjunto recursivamente enumerable) generados por gramáticas de tipo 0. Fue inventada en 1936 por Alan Turing.

Definición

Una Máquina de Turing (MT) es un modelo matemático que consiste en una cinta de longitud infinita dividida en celdas en las que se da entrada. Consta de un cabezal que lee la cinta de entrada. Un registro de estado almacena el estado de la máquina de Turing. Después de leer un símbolo de entrada, se sustituye por otro, se cambia su estado interno y se mueve de una celda a la derecha o a la izquierda. Si la MT alcanza el estado final, la cadena de entrada es aceptada, en caso contrario es rechazada.

Una MT puede describirse formalmente como una 7-tupla (Q, X, ∑, δ, q0, 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 × {Desplazamiento_izquierdo, Desplazamiento_derecho}.

• q0 es el estado inicial

• B es el símbolo de espacio en blanco

• F es el conjunto de estados finales

Comparación con el autómata anterior

La siguiente tabla muestra una comparación de las diferencias entre una máquina de Turing y un autómata finito y un autómata pushdown.

.

Ejemplo de máquina de Turing

Máquina de Turing M = (Q, X, ∑, δ, q0, B, F) con

• Q = {q0, q1, q2, qf}
• X = {a, b}
• ∑ = {1}
• q0 = {q0}
• B = símbolo en blanco
• F = {qf }

δ viene dado por –

Máquina	Estructura de datos de pila	¿Determinista?
Autómata finito	N.A	Sí
Autómata de empuje	Último en entrar, primero en salir(LIFO)	No
Máquina de Turing	Cinta infinita	Sí

.

1Lqf

Símbolo del alfabeto de la cinta	Estado presente ‘q0’	Presente Estado ‘q1’	Presente Estado ‘q2’
a	1Rq1	1Lq0
b	1Lq2	1Rq1

Aquí la transición 1Rq1 implica que el símbolo de escritura es 1, la cinta se mueve hacia la derecha, y el siguiente estado es q1. De forma similar, la transición 1Lq2 implica que el símbolo de escritura es 1, la cinta se mueve hacia la izquierda, y el siguiente estado es q2.

Complejidad temporal y espacial de una máquina de Turing

Para una máquina de Turing, la complejidad temporal se refiere a la medida del número de veces que se mueve la cinta cuando la máquina se inicializa para unos símbolos de entrada y la complejidad espacial 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)