EL TEMA Construccion Modular Maquina De Turing SE ENCUENTRA ESPERANDO TUS CONOCIMIENTOS. Las maquinas de Turing además de utilizarse para el reconocimiento de lenguajes, también se toman como modelos teóricos de las computadoras. Se puede combinar dos máquinas de Turing permitiendo que compartan la misma cinta y, que cuando una termine su ejecución, la otra empiece. El contenido de la cinta cuando comienza la ejecución de la segunda máquina de Turing, está formado por todo lo que dejó la primera máquina de Turing, y la cabeza de l/e de la segunda se situará, al comienzo de la ejecución, sobre la celda de la cinta sobre la que terminó la primera. EJEMPLO: Sea M1 dada por:
Q1 = {q1, q2,q3,q4}
S = ā
G = {a,Þ} s1 = q1
F1 = {q4}
y d dada por:
d1 (q1,a)= (q2,a,R)
d1 (q1,Þ)= (q2,Þ,R)
d1 (q2,a)= (q2,a,R)
d1 (q2,Þ)= (q3,Þ,L)
d1 (q3,Þ)= (q4,Þ,R)
d1 (q3,a)= (q4,a,R)
Sea M2 dada por:
Q2 = {p1, p2}
S = ā
G = {a,Þ} s2 = p1
F2 = {p4}
y d2 dada por:
d2 (p1,a)= (p2,a,R)
d2 (p1,Þ)= (p2,a,R)
Obsérvese que M1 busca el primer blanco que haya a la derecha de donde ha comenzado, mientras M2 escribe una a y para La a se escribe independientemente del contenido de la celda actual. Combinando estas dos maquinas de Turing obtenemos un dispositivo que primero busca hacia la derecha el primer Þ después escribe una a en todas las celdas. En seguida se definirá la combinación o composición de maquinas de Turing como sigue: Sean M1 y M2 dos maquinas de Turing sobre el mismo alfabeto de entrada y el mismo alfabeto de salida, donde:
M1 = (Q1,S,s1,F1,d1 ) y S,G,s2,F2,d2 )
Se supone que Q1 Ç Q2 = Ø. La composición de las máquinas de Turing M1 y M2 es la máquina de Turing S,G,s,F,d ) que se denota M 1 M 2?, donde: Q=Q1 È Q2 s = s1 F= F2
d1 (q,s), Si q Î Q1 y d1 (q,s) ¹ (p, t, X) para todo p Î F1
d (q,s) = d2 (q,s), Si q Î Q2
(d2,t,X), Si q Î Q1 y d1 (q,s) = (p, t, X) para algún p Î F1
tendrá las transiciones dadas mediante
d (q1,a)= (q2,a,R)
d (q1,Þ)= (q2,Þ,R)
d (q2,a)= (q2,a,R)
d (q2,Þ)= (q3,Þ,L)
d (q3,Þ)= (q4,Þ,R)
d (q3,a)= (q4,a,R)
d (p1,a)= (p2,a,R)
d (p1,Þ)= (p2,a,R)
con s= q1 t F= {p2} M1 busca el primer blanco que haya a la derecha de la posición actual de la cabeza. Consideremos una cinta:
a a a Þ a a Þ Þ Þ
£
Posición actual de la cabeza La maquina de Turing compuesta por M 1 M 1 terminará en la
a a a Þ a a Þ Þ Þ
£ Posición actual de la cabeza
mientras que las Máq. de Turing compuesta M 1 M 1 M 1 terminaría en la posición
a a a Þ a a Þ Þ Þ
Otra forma de especificar las transiciones es el uso de una tabla. La tabla sería la siguiente:
d (q,s) s ¹Þ s = Þ q1 (q2,s,R) (q2,Þ,R) q2 (q2,s,R) (q3,Þ,L) q3 (q4,s,R) (q4,Þ,R)
Una de las columnas especifica para un símbolo de la cinta en particular y la otra especifica el resto de símbolos de la cinta. La transición d (q2,s) = (q2,s,R) de la columna etiquetada con s ¹Þ indica que, para todo símbolo de la cinta s que sea distinto de Þ, la máquina de Turing escribe s en la cinta, se mueve a la derecha y permanece en el estado q2. La máquina de Turing cuya tabla de transición es
d s ¹Þ s = Þ q1 (q2,s,R) (q2,Þ,R) q2 (q2,s,R) (q3,Þ,L) q3 (q4,s,R) (q4,Þ,R) donde F= {q4} y S = q1. Esta máquina de Turing busca hacia la izquierda el primer símbolo de la cinta que no sea blanco y termina con la cabeza de lectura/escritura sobre dicha celda. Esta máquina de Turing será denotada por Lb (la b se usa para denotar “cualquier símbolo excepto b”). Combinando Lb y Rb, se obtiene Rt;Lb, donde la cabeza de lectura/escritura se sitúa sobre el símbolo de la cinta que precede al primer o que haya la derecha de la posición actual. Por tanto, si empezamos sobre
c a c Þ Þ a b
h
Posición de la cabeza
la máquina de Turing combinada terminaría en :
c a c Þ Þ a b
h
posición de la cabeza
En el Ejemplo vimos una máquina de Turing (M2) que escribía un Único símbolo como salida. Será conveniente especificar una máquina de Turing que escriba como salida un único símbolo, a, y que permanezca sobre dicha celda. Vamos a especificar esta máquina de Turing donde s = ql y F = { q3 } mediante la siguiente tabla:
d (q,s) sÎ Þ q1 (q2,a,R) q2 (q3,s,L)
Þ aR buscaría el primer Þ que hubiera a la derecha de la posición actual de la cabeza, escribiría una a en la celda y se movería a la siguiente celda por la derecha. Se desearía poder combinar las máquinas de Turing sencillas de modo que se consiguiera una máquina de Turing sencilla bajo unas condiciones determinadas. Por ejemplo, supongamos que L Þ R va seguida por una máquina que escriba una a si la celda es un blanco o escriba una b si la celda contiene una a. Se nace
sita bifurcar el camino de ejecución. Consideremos la máquina de Turing cuya tabla de transición es d s ¹Þ s = Þ q1 (q2,Þ,L) (q4,a,L) q2 (q3,Þ,R) (q3,a,R) q3 (q5,Þ,R) (q4,a,R) donde F = { q3, qs} y S = ql (obsérvese que no hay transiciones para q3 o q5). Su- pongamos que componemos esta máquina de Turing con las máquinas de Turing que escriben a y b de forma que, si termina en el estado q3, se inicia la ejecución de la máquina de Turing que escribe a y, si termina en el estado q5, la ejecución que comienza será la de la máquina de Turing que escribe b. Hemos provocado una bifurcación en la ejecución y se podría denotar mediante el diagrama
hemos representado la máquina de Turing que causa la bifurcación mediante las flechas. Por ejemplo, una máquina de Turing que analiza una cadena convirtiendo toda a en b y toda b en a, se podría representar
Obsérvese que hemos marcado con una flecha la máquina de Turing sencilla que comienza la secuencia de ejecución, al igual que hicimos con el estado inicial de un autómata finito. Es más, puesto que no hay ningún estado siguiente a R cuando el símbolo actual de la cinta es o, entonces en ese caso, la máquina compuesta se debería parar .
