Máquina de Turing

INFORMATICA UNIVERSIDAD

PROCESO

     Para el desarrollo de ejercicios prácticos es necesario contar con una serie de conocimietos previos referentes al tema de estudio. Las máquinas de Turing durante su procedimiento pueden considerarse como una 7-tupla de la siguiente forma:

M={Q, Σ, Γ, s, b, F, δ}

Donde cada uno de los parámetros son:

Q: Representa un conjunto finito de estados que puede atravesar un máquina de Turing dada.

Σ: Es el alfabeto formado por todos los símbolos que reconoce la máquina de Turing en cuestión.

Γ: Es un conjunto formado por la unión del alfabeto que maneja la máquina de Turing y un símbolo agregado denominado blanco. Se le llama también alfabeto de cinta ya que reconoce todos los símbolos que pueden estar escritos sobre la cinta que lee la máquina de Turing.

S: Es el estado inicial de la máquina de Turing. Es el estado donde comienza a operar la máquina de Turing.

b: Es el carácter considerado como el blanco de la cinta. Puede haber una cantidad infinita de este símbolo.

F: Es un conjunto de estados finales. Se dice que la máquina de Turing finalizo su operación exitosamente cuando se detiene en uno de estos estados.

δ: Es la función de transición de la máquina de Turing, Está descrita de la siguiente manera:

δ(q, x)=(p, y, d)

Lo que significa que si la máquina de Turing se encuentra con un símbolo “x” estando en el estado “q”, la máquina de Turing escribirá un símbolo “y” (reemplazando el anterior símbolo “x”) y se moverá en una dirección “d” (puede ser hacia la derecha o hacia la izquierda) mientras pasa al estado “q”.

 

En resumen, se puede considerar a las máquinas de Turing como un autómata capaz de reconocer lenguajes formales, lo cual lo hace más eficaz que un autómata de estado finito o un autómata de pila.

 

(Representación gráfica de una máquina de Turing funcionando)

 

A continuación, un ejemplo de un ejercicio práctico relacionados con el estudio de máquinas de Turing:

 

 

 

Problema

Enunciado:

Máquina de Turing que proporciona el complemento a 1 de un número binario.

 

Solución:

M=({q0,q1},{0,1},{0,1,B},q0, B ,{q1},δ)

Siendo δ la función de transición definida por:

δ(q0,0)=(q0,1,R)δ(q0,0)=(q0,1,R)

δ(q0,1)=(q0,0,R)δ(q0,1)=(q0,0,R)

δ(q0,B)=(q1,B,R)

Explicación:

La esta máquina de Turing reemplazará todos los 1´s y 0´s de una cadena por su complemento, es decir 0’s y 1’s respectivamente, comenzando desde el extremo izquierdo de la cadena y dirigiéndose siempre hacia el extremo derecho. La máquina finalizará su operación al llegar al primer símbolo en blanco (B) al final de la cadena.

(Puede quitar la publicidad ampliando la cuenta)