Maquinas De Turing

Si L es reconocido por una MT multicinta entonces L es reconocido por una m´quina a de Turing de una sola cinta. Se supone que la MT M dispone de k cintas, acepta el lenguaje L, y simulamos M mediante una MT N de una sola cinta, soponiendo 2k pistas.

EISC

M´quinas de Turing a

Si La MT multicinta tiene k = 2 cintas se dispone de una MT de una sola cintas de 2k = 4 pistas, las pistasprimera y tercera tienen la informaci´n de las dos cintas. Las o pistas segunda y cuarta tienen las cabezas. Para simular un movimiento M , la cabeza de N usamos un marcador para las cabezas de la cintas y si hay un desplazamiento a la derecha en M , entonces reemplazamos el 1 en N por B y viceversa si hay un desplazamiento en la izquierda, el reemplazo de 1 por B y B por 1 hace la simulaci´n de loscabezales o de M .

EISC

M´quinas de Turing a

EISC

M´quinas de Turing a

M´quina de Turing no deterministas a Se diferencia de las MT deterministas por la funci´n δ, que para cada caso q y para o cada s´ ımbolo de cinta X: δ(q, X) = {(q1, Y1, S1), (q2, Y2, S2), . . . (qk , Yk , Sk )} para cualquier k entero postivo finito. Observaci´n 5 o Ambos modelos tienen el mismo podercomputacional. Teorema 2 El lenguaje L es reconocido por una M´quina a de Turing No Determinista ⇔ L es reconocido por una m´quina de Turing Determinista. a Observaci´n 6 o

EISC

M´quinas de Turing a

Ambos modelos tienen el mismo poder computacional.

1. ⇐) Si L es reconocido por una MTD entonces L es reconocido por una M´quina de Turing a No Determinista. las MTD son m´quinas de Turing No aDeterministas en las que hay una transici´n por cada estado/s´ o ımbolo.

2. ⇒) Si L es reconocido por una M´quia na de Turing NO determinista entonces L es reconocido por una M´quina a de Turing Determinista. Podemos simular una MTND con una MT determinsta de tres cintas: a) Se obtiene un n que es el n´meu ro m´ximo de opciones asociada a a cada transici´n. o b) En la primera cinta va la cadena deentrada.

EISC

M´quinas de Turing a

c) En la segunda cinta se generan las cadenas sobre el alfabeto {1, 2, . . . , n} por orden num´rico. e 1) Todas las cadenas de longitud 1. 1, 2, 3, . . . , n 2) Todas las cadenas de longitud 2. 11, 12, 13, . . . , 1n, 21, 22, 23, . . . , 2n, n1, n2,

n3, . . . , nn 3) Todas las cadenas de longitud 3. 111, 112, 113, . . . , 11n, 121, 122, 123, . . . ,12n, 1n1, 1n2, 1n3, . . . , 1nn Al final todas las cadenas de todas las longitudes deben ir en la cinta 2 en orden lexicogr´fico. a

EISC

M´quinas de Turing a

d) En la tercera cinta se realiza la simulaci´n, cada vez que se geneo ra una secuencia en la cinta 2, se copia la cadena de entrada en la cinta 3 y simula computaci´n del o MTND. δ(q, (a, 1, B)) = (p, (a, 1, a), (D, D, D)) e) La MTDprueba todas las combinaciones de la cinta dos, empezando cada vez que una configuraci´n o cuando no sirva. Si la cadena es reconocida en el MTND tambi´n es e reconocida en el MTD multicinta. Ejemplo 8 Sea el siguiente MT no determin´ ıstico.

EISC

M´quinas de Turing a

1 1

2

δ(q0, a) = {(q0, a, D), (q1, a, D)} δ(q1, b) = {(q1, b, D)}
1

δ(q1, B) = {(q2, B, D)} si se va hareconocer la cadena la MTND hace esta derivaci´n: o q0 a aq1B aBq2B

y la cadena es reconocida pero si se va por el otro camino q0 a aq0B

llegar´ a una transici´n no existente. ıa o Entonces hay una probabilidad que una de las secuencias de la cinta 2 que reconoce la cadena a sea: 1,1,1

EISC

M´quinas de Turing a

algunas transiciones que pueden simular el MTND ser´ ıan: δ(q0, (a, 1, B)) =(q1, (a, 1, a), (D, D, D) δ(q1, (B, ∗, B)) = (q5, (B, ∗, B), (I, N, I) δ(q5, (a, ∗, a)) = (q5, (a, ∗, B), (I, N, I) δ(q5, (B, ∗, B)) = (q0, (B, ∗, B), (D, D, D) δ(q0, (a, ∗, B)) = (q5, (a, ∗, B), (D, D, D) δ(q5, (B, 2, B)) = (q5, (B, 2, B), (I, N, I) δ(q5, (a, 2, B)) = (q5, (a, 2, a), (D, D, D) En la transici´n o δ(q0, (a, 1, B)) = (q1, (a, 1, a), (D, D, D), el 1 de (a, 1, B) significa que se...