mc_tema7

Tema 7Mquinas de Turing

Gabriel Navarro

Modelos de ComputacinGrado en Ingeniera Informtica

Gabriel Navarro Tema 7 Mquinas de Turing

Introduccin

en los temas anteriores hemos estudiado...

Lenguajes sencillos (regulares, libres de contexto)y sus utilidades prcticas en compiladores, bsquedas entextos, escneres, codificacin,...y unas mquinas tericas que reconocen estos lenguajes

ahora cambiamos de direccin...


Mquinas de Turing

Mquinas de TuringMs generales que AF y APReconocen los lenguajes recursivamente enumerablesNo se inventaron con el mismo proposito que los AF y APSe buscaban los lmites de clculo


Mquinas de Turing

Las mquinas de Turing se pueden representar de forma intuitivacomo un dispositivo mecnico, formado por:

una cinta infinita, dividida en celdasun cabezal de lectura-escritura que se mueve sobre dichacinta tanto a derecha como a izquierda


Mquinas de Turing

CintaLa cinta de entrada es una secuencia infinita de celdas. En cadacelda de la cinta solo se puede almacenar un smbolo. Las celdasque no estn ocupadas, estn vacas, las vamos a denotar por elcarcter # (smbolo en blanco).


Mquinas de Turing

CabezaLa MT posee una cabeza que puede emplearse para leer y escribirsmbolos en la cinta de la mquina. As, puede rastrear los datos dela cinta y modificar las celdas que desee sin alterar las dems. Poreso, una mquina de Turing puede estar en movimientoindefinidamente.

AccionesLas acciones especficas son operaciones de escritura y demovimientoLa operacin de escritura consiste en reemplazar un smbolo enla cinta con otro smbolo y luego cambiar de estadoLa operacin de movimiento comprende mover la cabeza unacelda a la derecha o a la izquierda y luego pasar a un nuevoestado. Dependera del smbolo de la celda y del estado actual


Mquinas de Turing

A Turing Machine - Overviewhttp://www.youtube.com/watch?v=E3keLeMwfHY&feature=related


Definicin: Mquina de Turing

Una mquina de Turing se define por la siguiente tupla:

MT = (, ,#,Q, q0, f ,F )

donde es el alfabeto de smbolos de entrada, distintos de # es el alfabeto de smbolos de la cintaComo la MT puede escribir en la cinta, es diferente el alfabetode los smbolos que inicialmente pueden aparecer en la cintadel alfabeto de los smbolos que, en algn momento, puedenaparecer en la cinta. Esto es, .# es un smbolo de la cinta de entrada especial que representael espacio en blanco

# / ,#



Una mquina de Turing se define por la siguiente tupla:

MT = (, ,#,Q, q0, f ,F )

dondeQ es el conjunto de estadosq0 Q es el estado inicialf es una funcin parcial que se llama funcin de transicin

f : Q Q {I ,D}

Decimos que f es una funcin parcial porque puede que notenga imagen para algn par de Q F Q es el conjunto de estados parada. F puede ser elconjunto vaco.



Ejemplo:Inicialmente la cinta contiene un nmero finito de smbolos,precedidos y seguidos por infinitos espacios en blanco

Supongamos que tenemos la transicin f (q0, a) = (q3, c ,D)

La MT transita al estado q3, reemplaza el smbolo a por elsmbolo c y se desplaza una posicin a la derecha



Ejemplo

Sea (, ,#,Q, q0, f ,F ) la mquina de Turing = {a, b} = {a, b,#}Q = {q0, q1}F = {q1}

f a b #q0 (q0, a,D) (q0, a,D) (q1,#, I )q1



EjemploPartimos de una configuracin inicial y representamos medianteunos grficos las distintas etapas del proceso de lectura de la MT


Configuracin instantnea

Configuracin instantneaUna configuracin instantnea viene determinada por elestado actual, el contenido de la cinta y la posicin de lacabeza sobre la cinta.Una forma sencilla de notarla viene dada por una cadena deltipo:

a1a2 akqiak+1 anLa cabeza de la mquina se coloca sobre la celda que contieneak+1 y el estado actual es qi .Para el ejemplo anterior, los pasos de clculo seran:

q0abba aq0bba aaq0ba aaaq0a aaaaq0# aaaq1a


Computacion

Puesto que la funcin de transicin f es una funcin parcial, puededarse el caso que f (q, a) quede indefinido. Por tanto es imposibleque la mquina de Turing pase a otra configuracin. Entonces sedice que la MT est parada.La otra forma de que la mquina de Turing est parada es quellegue a un estado de parada

ComputacinLa secuencia de todos los movimientos que conducen a la MT auna configuracin de parada se llama computacin.


Lenguaje aceptado

Aceptacin de lenguajesUna mquina de Turing se puede comportar como un aceptador deun lenguaje, de la misma forma que lo hacan los AF y los AP. Paraevaluar una cadena:

Registramos la cadena en la cinta de la mquinaColocamos la cabeza de la mquina en la celda del extremoizquierdoPonemos en marcha la mquina a partir de su estado inicial


Lenguaje aceptado

Aceptacin de lenguajesLa decisin de si una cadena es reconocida por una mquina deTuring depende de si:

F = . Decimos que la mquina acepta la cadena porestado de aceptacin, si despus de una secuencia demovimientos, la mquina de Turing llega a un estado deparada (y por tanto, se para).F = . Diremos que la mquina acepta una cadena porparada si es capaz de parar. Es decir, si una cadena no esreconocida, la mquina entra en un bucle infinito y no paranunca.

A diferencia de los AF y AP, una MT no necesita leer toda lacadena para decidir si pertenece o no a un lenguaje


Lenguaje aceptado

Lenguaje aceptadoLa coleccin de cadenas aceptadas por una mquina de Turing Mse llama lenguaje aceptado por la mquina de Turing (M).

Se dice que un lenguaje L es un lenguaje aceptado por unamquina de Turing si existe un MT M tal que L = (M).


Ejemplos

El lenguaje de las palabras con un nmero par de ceros

{{0, 1}, {0, 1,#}, {q0, q1, q2}, q0, f , {q2}}f (q0, 0) = (q1,#,D) f (q0, 1) = (q0,#,D)f (q1, 0) = (q0,#,D) f (q1, 1) = (q1,#,D)f (q1,#) = (q1,#, I ) f (q0,#) = (q2,#, I )


Ejemplos

El lenguaje {anbn con n 1}{{a, b}, {a, b,A,B,#}, {q0, q1, q2, q3, q4}, q0, f , {q4}}

f (q0, a) = (q1,A,D) f (q1, a) = (q1, a,D)f (q1,B) = (q1,B,D) f (q1, b) = (q2,B, I )f (q2,B) = (q2,B, I ) f (q2, a) = (q2, a, I )f (q2,A) = (q0,A,D)f (q0,B) = (q3,B,D) f (q3,B) = (q3,B,D)f (q3,#) = (q4,#,D)


Ejemplos

El lenguaje {anbncn con n 1}

{{a, b, c}, {a, b, c ,X ,Y ,Z ,#}, {q0, qa, qb, qc , qY , qZ , qf }, q0, f , {qf }}f a b c X Y Zq0 (qa,X ,D) (qY ,Y ,D) qa (qa, a,D) (qb,Y ,D) (qa,Y ,D) qb (qb, b,D) (qc ,Z , I ) (qb,Z ,D)qc (qc , a, I ) (qc , b, I ) (q0,X ,D) (qc ,Y , I ) (qc ,Z , I )qY (qY ,Y ,D) (qZ ,Z ,D)qZ (qZ ,Z ,D)

f (qZ ,#) = (qf ,#,R)


Lenguajes aceptados por un MT

Lenguaje recursivamente enumerableLos lenguajes aceptados por una mquina de Turing se llamanlenguajes recursivamente enumerables

Esta es una clase de lenguajes ms amplia que los lenguajesindependientes de contexto

Reg LIC LRE


Lenguajes aceptados por un MT

Lenguaje recursivoUn lenguaje que es aceptado por una MT de manera que se produceuna parada para todas y cada una de las cadenas que se dan comoentrada a la mquina, se conocen como lenguajes recursivos.

Los lenguajes recursivos tambin forman una clase mayor que la delos lenguajes independientes del contexto

Reg LIC LR LRE


Gramticas y MT

TeoremaPara toda gramtica de tipo 0, existe una mquina de Turing quereconoce el lenguaje generado por dicha gramtica

TeoremaPara toda mquina de Turing, existe una gramtica de tipo 0 quegenera un lenguaje igual al reconocido por la mquina de Turing


Autmata lineal acotado

Un autmata lineal acotado es una MT cuya cinta es finita,concretamente,

Autmata lineal acotadoUn ALA es una MT (, ,#,Q, q0, f ,F ) donde:

Tendr que realizar su computacin nicamente en las celdasocupadas originariamente por la cadena de entrada, utilizandopor consiguiente una cinta de entrada limitada, y no ilimitadacomo es el caso de la Mquinas de Turing generalesPresenta dos smbolos de cinta y que marcan el principio yfinal de cintaLa mquina no se puede mover a la izquierda de , ni a laderecha Los smbolos y no pueden ser sobreescritos


Autmata lineal acotado

Lenguaje aceptadoLos lenguajes aceptados por un ALA son los lenguajesdependientes del contexto. Recprocamente, dado un lenguajedependiente del contexto existe un ALA que lo acepta

Reg LIC LDC LR LRE


Jerarqua de Chomsky

Lenguaje Gramtica Mquina TericaRegular Tipo 3 Autmata FinitoLibre de Contexto Tipo 2 Autmata con pilaDependiente del Contexto Tipo 1 Autmata lineal acotadoRecursivo - Mquina de Turing que paraRecursivamente enumerable Tipo 0 Mquina de Turing


Variaciones de una MT

Con la misma potencia de clculoMquina de Turing no deterministaMquina de Turing con cinta infinita slo a un ladoMquina de Turing multicintaMquina de Turing multidimensional


Por qu MT?

Lmites de clculoEs un mdelo para establecer qu es posible calcular y qu no. Esun modelo de computacin

Problemas de decisinEs un problema que ante cualesquiera datos de entrada la respuestaes s o no

No es muy restrictivoTodos los problemas se pueden escribir como un problema dedecisin


Por qu MT?


EjemploConjetura de Goldbach: Todo nmero par mayor que 2 puedeescribirse como suma de dos nmeros primos

bool Goldbach (int n){for (int i=2;i

Por qu MT?


Problemas de decisinEn general, un problema de decisin cualquiera se puede representarpor un lenguaje

Turing-computableUn problema ser Turing-computable si su lenguaje es aceptadouna MT. Esto es, si es recursivamente enumerable


Por qu MT?

No es el nico modelo de computacin-clculoJuego de la vidaFunciones recursivas parciales...

aunque las propuestas serias son todas equivalentes

Tesis de Turing-ChurchEl poder computacional de una mquina de Turing es tan grandecomo el de cualquier sistema computacional posible (por ejemplo,los ordenadores actuales)


Por qu MT?

AlgoritmoUna MT que siempre para es una forma de definir la nocin dealgoritmo

Problemas decidiblesUn problema que es resuelto por una mquina de Turing quesiempre para se llama decidible

es decir, su lenguaje asociado es recursivoes decir, existe un algoritmo que lo resuelve


Por qu MT?


Problemas indecidiblesUn problema para el que NO existe una mquina de Turing que parese llama indecidible. Es decir, su lenguaje asociado NO es recursivo


Por qu MT?


Es decir

Problemas

indecidibles{

no Turing-computable (no rec. enum.)Turing-computable

decidibles (recursivos)


Lenguajes que no son recursivamente enumerables

PreguntaExisten lenguajes que no son recursivamente enumerables?

RespuestaEl lenguaje diagonal Ld




Codificacin de mquinas de Turing

Para una MT, M = ({0, 1},Q, {0, 1,B}, f , q1,B, {q2}) (no esrestrictivo)

0 = x1 codifica a 01 = x2 codifica a 00B = x3 codifica a 000qi codifica a 0i

D = D1 codifica a 0I = D2 codifica a 00




Codificacin de mquinas de Turing

Para una MT, M = ({0, 1},Q, {0, 1,B}, f , q1,B, {q2}) (no esrestrictivo)

Cada transicin se codifica de la manera:

f (qi , xj) = (qk , xl ,Dm) 0i10j10k10l10m

La mquina M se codifica a

111Transicion111Transicion211Transicion3....Transicionn111




Codificacin de mquinas de TuringPor ejemplo,

f (q1, 1) = (q3, 0,R)f (q3, 0) = (q1, 1,R)f (q3, 1) = (q2, 0,R)f (q3,B) = (q3, 1, L)

codifica a

11101001000101001100010101001001100010010010100110001000100010010111

De esta manera, cada MT es un nmero entero en binario




Construccin de LdSe numeran las MT (1,2,3,...)Se numeran las cadenas de {0, 1}*Se construye la tabla T , donde T [i ][j ] es 1 si i es aceptadapor j y 0, si no lo es

1 2 3 4 1 0 1 1 0 2 1 0 1 1 3 1 1 1 0 ...

......

......

. . .




Construccin de LdLd est formado por las cadenas i que no son reconocidas porla MT i , es decir, las cadenas cuya fila tiene en la diagonal uncero

1 2 3 4 1 0 1 1 0 2 1 0 1 1 3 1 1 1 0 ...

......

......

. . .




Ld no es recursivamente enumerableSi lo fuera, entonces Ld es reconocido por la MT j-sima, paracierto j > 0. Esto es, Ld = (Mj).Pero,

si j Ld entonces (j , j) = 0, luego j / (Mj)si j / Ld entonces (j , j) = 1, luego j (Mj)

En ambos casos, se llega a una contradiccion. Luego Ld no esrecursivamente enumerable


Lenguajes recursivamente enumerables

PreguntaExisten lenguajes recursivamente enumerables que no sonrecursivos? Esto es, existen problemas para los que no hay unalgoritmo que los resuelva pero que son Turing-computables?

Problema de la paradaSea M una mquina de Turing y una cadena w , para M conentrada w?




No es decidibleSi existiese un algoritmo bool PARA(M,w) donde:

M es la codificacin de la MTw la cadena

puedo construir

bool Diagonal (M){if (PARA(M,M))

while (1){}else

return 1;}




No es decidibleEsto es,

Diagonal(M) termina si y slo si M(M) nunca termina

Si usamos M=Diagonal

Diagonal(Diagonal) termina si y slo si Diagonal(Diagonal)nunca termina

lo cual es una contradiccion, por lo que PARA no puede existir

Sin embargo, el lenguaje asociado es recursivamente enumerable



Otro ejemplo (Hopcroft-Motwani-Ullman, Introduction to...)

Usando la codificacin de mquinas de Turing:Le = {M mquina de Turing tal que (M) = }Lne = {M mquina de Turing tal que (M) = }

se tiene que:Le no es recursivamente enumerableLne es recursivamente enumerable no recursivo...sin embargo, uno es el complementario de otro...


Problemas indecidibles

Algunos problemas indecidiblesComprobar,

si dos LIC son el mismo lenguajesi una LIC es un lenguaje regularsi un LIC es inherentemente ambiguosi una GIC es ambiguasi la interseccin de dos LIC es el vacosi el lenguaje aceptado por una MT es vaco


Problemas indecidibles

Otros problemas indecidibles10o problema de HilbertEl problema de la Correspondencia de PostHilbert EntscheidungsproblemThe mortal matrix problem


Problemas tratables e intratables

Aunque un problema sea decidible, puede que el clculo delalgoritmo que lo resuelve no se obtenga en un tiempo razonable

Tiempo de ejecucin

Llamamos tiempo de ejecucin T (M,w) de una MT M para laentrada w , al nmero de pasos que M ejecuta antes de pararse

Funcin de ejecucinLa funcin de ejecucin de un MT M, T : N N, se define por

T (n) = max{T (M,w) con |w | = n}


Problemas tratables e intratables

Aunque un problema sea decidible, puede que el clculo delalgoritmo que lo resuelve no se obtenga en un tiempo razonable

Problema tratableUn problema decidible es tratable si es resuelto por una MT contiempo de ejecucin polinomial

Problema intratableUn problema decidible es intratable si no es tratable


=

La clase Un problema decidible est en la clase si es resuelto por un MTdeterminista en tiempo polinomial

La clase Un problema decidible est en la clase si es resuelto por unMT no determinista en tiempo polinomial


=

Es obvio que Problema del milenio (1000000 $, Clay Mathematics Institute)

= ?


mc_tema7

Documents