Wikipedia

Resultados de la búsqueda

martes, 26 de septiembre de 2017

TRES EJEMPLOS DE MAQUINAS DE TURING



EJEMPLO 1: DISEÑAR UNA MAQUINA DE TURING QUE ACEPTE EL LENGUAJE
L={0n1n :n>0}


Lo primero que haremos es limitar el alfabeto a
Σ={0,1}
así nos aseguramos de que sólo puede aceptar palabras con de entrada con símbolos 1 y 0.
Los símbolos de cinta serán
T={0,1,B,X,Y}
siendo B el símbolo en blanco.
La MT consta de cinco estados:
q0,q1,q2,q3,q4
Los estados q0 y q4 son el inicial y el final, respectivamente.
Inicialmente, la cabeza señala el primer 0. Lo cambia por X y se desplaza a la derecha en busca del primer 1 para cambiarlo por Y:
δ(q0,0)=(q1,X,R)
δ(q1,0)=(q1,0,R)
Es decir, mientras haya 0's, se mantiene en el estado q1 .
δ(q1,1)=(q2,Y,L)
Ha encontrado el primer 1. Lo cambia por Y y pasa al estado q2 moviéndose a la izquierda. En este estado, la MT se mueve hacia la izquierda en busca de X saltando las casillas con 0's:
δ(q2,0)=(q2,0,L)
Cuando encuentra la X, se mueve hacia la derecha esperando encontrar un 0 para cambiarlo por X, por lo que pasa al estado q:
δ(q2,X)=(q0,X,R)
Una vez cambiado dicho 0 por X, está en el estado q. Ahora tiene que buscar el siguiente 1 y cambiarlo por Y, pero se encuentra con Y antes de llegar, por lo que tiene que saltar esta casilla:
δ(q1,Y)=(q3,Y,R)
En el estado q3 sigue saltando las casillas con Y hasta llegar al 1:
δ(q3,Y)=(q3,Y,R)
δ(q3,1)=(q2,Y,L)
Pasa al estado q2 una vez ha cambiado el 1 por la Y. En este estado, la MT se mueve a la izquierda hasta encontrar una X. Una vez la encuentra, se mueve una casilla a la derecha. Si hay un 0, tendrá que empezar el proceso anterior (buscar 1, cambiarlo por Y y volver a buscar la X, con lo que estaremos de nuevo en este punto). Si ya no quedan 0's, habrá una Y y, por tanto, se han cambiado n 0's por n 's y n 1's por n 's. Entonces se mueve a la izquierda:
δ(q2,Y)=(q2,Y,L)
Se encuentra con una X y pasa al estado q0. En este estado se busca un 0 para cambiarlo por X, pero suponemos que ya no quedan. Entonces la cabeza debe moverse a la derecha para comprobar que tampoco quedan más 1's:
δ(q0,Y)=(q0,Y,R)
Cuando encuentra el primer símbolo en blanco, la MT finaliza:
δ(q0,B)=(q4,B,R)

En el caso de que haya más 0's que 1's, llegará un momento en el que ya no queden 1's (los habrá cambiado por ). La MT se quedará permanentemente en el estado q1 .
El diagrama de la MT es
diagrama de la máquina de Turing que acepta el lenguaje (0^n)(1^n)
Vamos a simular la MT para una sola entrada que todas tienen la misma forma. Mostraremos el estado final de la cinta y la posición de la cabeza (sombreado en color rosa).
Entrada: 000111; Resultado esperado: XXXYYY.
simulación de la Máquina de Turing

  • EJEMPLO 2: DISEÑAR UNA MAQUINA DE TURING QUE CALCULA EL NUMERO CONSECUTIVO DE UN NUMERO DADO EN BINARIO

Si el número es par, su último bit es 0. La máquina sólo tiene que cambiar este 0 por un 1.
Si el número es impar, su último bit es 1. En este caso, se tiene que cambiar por 0’s todos los 1’s seguidos que haya escritos de derecha a izquierda hasta llegar al primer 0, que se cambia por un 1. Si no hay ningún 0, entonces se tiene que añadir un 1 delante del número (añadir un bit). Es decir, escribir un 1 en la casilla en blanco (B) a la izquierda del número.
Vamos a considerar tres estados:
q0,q1,q2
  • Inicialmente, la MT está en el estado q0 con la cabeza señalando la primera cifra del número.
    La MT recorre todo el número para ver si es par o impar sin modificar su cinta.
    δ(q0,0)=(q0,0,R)
    δ(q0,1)=(q0,1,R)
  • Notemos que, por ahora, la MT se detiene al llegar al primer símbolo en blanco a la derecha del número.
    La MT vuelve a la anterior casilla (último número). Si es un 0, lo cambia por un 1 y pasa al estado final que es q. Para hacer esto usaremos el estado q:
    δ(q0,B)=(q1,B,L)
    δ(q1,0)=(q2,1,R)
  • Si el número es impar, la MT no ha cambiado el último número, pero está en el estado q. Tiene que cambiar todos los 1's consecutivos que haya de derecha a izquierda.
    δ(q1,1)=(q1,0,L)
  • Por ahora, la MT se para cuando llega al primer 0 (de derecha a izquierda) ó en un símbolo en blanco. Si es un 0, lo cambia por un 1 y el proceso finaliza:
    δ(q1,0)=(q2,1,L)
    (Hemos escrito un desplazamiento a la izquierda, pero esto no tiene importancia ya que la MT ha llegado al estado final).
  • Si lo que señala la cabeza es un blanco en vez de un 1, tiene que cambiarlo por un 1 y finalizar el proceso.
    δ(q1,B)=(q2,1,L)
El diagrama de la máquina es
diagrama de la Máquina de Turing
Donde el cuadro representa el símbolo en blanco B.
Vamos a simular la MT para varias entradas. Mostraremos el estado final de la cinta y la posición de la cabeza (sombreado en color rosa).
Entrada: 000; Resultado esperado: 001.
simulación de la Máquina de Turing
Entrada: 0011; Resultado esperado: 0100.
simulación de la Máquina de Turing
Entrada: 111; Resultado esperado: 1000.
simulación de la Máquina de Turing
Entrada: 1; Resultado esperado: 10.
simulación de la Máquina de Turing



  • EJEMPLO 3: DISEÑAR UNA MAQUINA DE TURING QUE, DADA UNA PALABRA W DEL ALFABETO Σ={0, 1}, PROPORCIONA SU REVERSO, wR .

Lo que tiene que hacer la MT es cambiar el orden de los símbolos que hay en su cinta.
Usaremos los símbolos de cinta adicionales A y Z para indicar el comienzo y el final de la palabra w en la cinta.
En el estado q, la MT busca el comienzo de palabra, es decir, el primer símbolo en blanco a la izquierda. Cuando lo encuentra, lo cambia por A:
δ(q0,0)=(q0,0,L)
δ(q0,1)=(q0,1,L)
En el estado q1 la MT se desplaza hacia la derecha hasta encontrar el primer símbolo en blanco para cambiarlo por Z:
δ(q1,0)=(q1,0,R)
δ(q1,1)=(q1,1,R)
δ(q1,B)=(q2,Z,L)
Luego pasa al estado q. En este estado, cambia el primer elemento de la palabra w (o sea, el último) por B para escribirlo al lado derecho de Z.
Como usaremos este estado posteriormente, puede ocurrir que ya no queden símbolos de wporque ya se ha copiado. En este caso sólo quedarán símbolos en blanco y el símbolo A que marca el comienzo de w:
δ(q2,B)=(q2,B,L)
δ(q2,A)=(q8,B,L)
δ(q2,1)=(q3,B,R)
δ(q2,0)=(q6,B,R)
En el caso de que ya no haya símbolos de w, la MT borra A y vuelve pasa al estado q8 en el que buscará la Z para borrarla de la cinta, pasando al estado final q:
δ(q8,B)=(q8,B,R)
δ(q8,Z)=(q9,B,R)
Volviendo al punto anterior, si en q2 se encuentra con el símbolo 1, entonces lo borra y entra en los estados q3 y q4 cuya finalidad son escribir el 1 en su sitio correspondiente a la derecha de Z:
δ(q3,B)=(q3,B,R)
δ(q3,Z)=(q4,Z,R)
δ(q4,B)=(q5,1,R)
δ(q4,0)=(q4,0,R)
δ(q4,1)=(q4,1,R)
En el estado q5 la MT busca de nuevo el símbolo Z para pasar de nuevo al estado q:
δ(q5,0)=(q5,0,L)
δ(q5,1)=(q5,1,L)
δ(q5,Z)=(q2,Z,L)
El otro caso es que en q2 se encuentre con el símbolo 0. La MT procede de forma análoga a los estados q3 y q4 pero escribiendo 0 en vez de 1. Para ello usaremos los estados q6 y q7:
δ(q6,B)=(q6,B,R)
δ(q6,Z)=(q7,Z,R)
δ(q7,B)=(q5,0,L)
δ(q7,0)=(q7,0,R)
δ(q7,1)=(q7,1,R)
Finalmente, en la cinta sólo quedará la palabra wR, es decir, la palabra w escrita de derecha a izquierda.
El diagrama de la máquina de Turing es
máquina de Turing que cambia el orden de una palabra