Las maquinas de turing

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 quedejó 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érveseque 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 deTuring 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= F2d1 (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 porM 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)...