Mc_tema7.pdf

Tema 7 Máquinas de Turing Gabriel Navarro

Modelos de Computación Grado en Ingeniería Informática

Gabriel Navarro

Tema 7 Máquinas de Turing

Introducción

en los temas anteriores hemos estudiado... Lenguajes sencillos (regulares, libres de contexto) y sus utilidades prácticas en compiladores, búsquedas en textos, escáneres, codificación,... y unas máquinas teóricas que reconocen estos lenguajes ahora cambiamos de dirección...

Gabriel Navarro

Tema 7 Máquinas de Turing

Máquinas de Turing

Máquinas de Turing Más generales que AF y AP Reconocen los lenguajes recursivamente enumerables No se inventaron con el mismo proposito que los AF y AP Se buscaban los límites de cálculo

Gabriel Navarro

Tema 7 Máquinas de Turing

Máquinas de Turing Las máquinas de Turing se pueden representar de forma intuitiva como un dispositivo mecánico, formado por: una cinta infinita, dividida en celdas un cabezal de lectura-escritura que se mueve sobre dicha cinta tanto a derecha como a izquierda

Gabriel Navarro

Tema 7 Máquinas de Turing

Máquinas de Turing

Cinta La cinta de entrada es una secuencia infinita de celdas. En cada celda de la cinta solo se puede almacenar un símbolo. Las celdas que no están ocupadas, están vacías, las vamos a denotar por el carácter # (símbolo en blanco).

Gabriel Navarro

Tema 7 Máquinas de Turing

Máquinas de Turing Cabeza La MT posee una cabeza que puede emplearse para leer y escribir símbolos en la cinta de la máquina. Así, puede rastrear los datos de la cinta y modificar las celdas que desee sin alterar las demás. Por eso, una máquina de Turing puede estar en movimiento indefinidamente. Acciones Las acciones específicas son operaciones de escritura y de movimiento La operación de escritura consiste en reemplazar un símbolo en la cinta con otro símbolo y luego cambiar de estado La operación de movimiento comprende mover la cabeza una celda a la derecha o a la izquierda y luego pasar a un nuevo estado. Dependera del símbolo de la celda y del estado actual Gabriel Navarro

Tema 7 Máquinas de Turing

Máquinas de Turing

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

Gabriel Navarro

Tema 7 Máquinas de Turing

Definición: Máquina de Turing Una máquina de Turing se define por la siguiente tupla: MT = (Σ, Γ, #, Q, q0 , f , F ) donde Σ es el alfabeto de símbolos de entrada, distintos de # Γ es el alfabeto de símbolos de la cinta Como la MT puede escribir en la cinta, es diferente el alfabeto de los símbolos que inicialmente pueden aparecer en la cinta del alfabeto de los símbolos que, en algún momento, pueden aparecer en la cinta. Esto es, Σ ⊂ Γ. # es un símbolo de la cinta de entrada especial que representa el espacio en blanco #∈ / Σ, # ∈ Γ Gabriel Navarro

Tema 7 Máquinas de Turing

Definición: Máquina de Turing Una máquina de Turing se define por la siguiente tupla: MT = (Σ, Γ, #, Q, q0 , f , F ) donde Q es el conjunto de estados q0 ∈ Q es el estado inicial f es una función parcial que se llama función de transición f : Q × Γ −→ Q × Γ × {I , D} Decimos que f es una función parcial porque puede que no tenga imagen para algún par de Q × Γ F ⊂ Q es el conjunto de estados parada. F puede ser el conjunto vacío. Gabriel Navarro

Tema 7 Máquinas de Turing

Definición: Máquina de Turing Ejemplo: Inicialmente la cinta contiene un número finito de símbolos, precedidos y seguidos por infinitos espacios en blanco

Supongamos que tenemos la transición f (q0 , a) = (q3 , c, D)

La MT transita al estado q3 , reemplaza el símbolo a por el símbolo c y se desplaza una posición a la derecha Gabriel Navarro

Tema 7 Máquinas de Turing

Definición: Máquina de Turing

Ejemplo Sea (Σ, Γ, #, Q, q0 , f , F ) la máquina de Turing Σ = {a, b} Γ = {a, b, #} Q = {q0 , q1 } F = {q1 } f a b # q0 (q0 , a, D) (q0 , a, D) (q1 , #, I ) q1 − − −

Gabriel Navarro

Tema 7 Máquinas de Turing

Definición: Máquina de Turing

Ejemplo Partimos de una configuración inicial y representamos mediante unos gráficos las distintas etapas del proceso de lectura de la MT

Gabriel Navarro

Tema 7 Máquinas de Turing

Configuración instantánea Configuración instantánea Una configuración instantánea viene determinada por el estado actual, el contenido de la cinta y la posición de la cabeza sobre la cinta. Una forma sencilla de notarla viene dada por una cadena del tipo: a1 a2 · · · ak qi ak+1 · · · an La cabeza de la máquina se coloca sobre la celda que contiene ak+1 y el estado actual es qi . Para el ejemplo anterior, los pasos de cálculo serían: q0 abba ⊢ aq0 bba ⊢ aaq0 ba ⊢ aaaq0 a ⊢ aaaaq0 # ⊢ aaaq1 a

Gabriel Navarro

Tema 7 Máquinas de Turing

Computacion

Puesto que la función de transición f es una función parcial, puede darse el caso que f (q, a) quede indefinido. Por tanto es imposible que la máquina de Turing pase a otra configuración. Entonces se dice que la MT está parada. La otra forma de que la máquina de Turing esté parada es que llegue a un estado de parada Computación La secuencia de todos los movimientos que conducen a la MT a una configuración de parada se llama computación.

Gabriel Navarro

Tema 7 Máquinas de Turing

Lenguaje aceptado

Aceptación de lenguajes Una máquina de Turing se puede comportar como un aceptador de un lenguaje, de la misma forma que lo hacían los AF y los AP. Para evaluar una cadena: Registramos la cadena en la cinta de la máquina Colocamos la cabeza de la máquina en la celda del extremo izquierdo Ponemos en marcha la máquina a partir de su estado inicial

Gabriel Navarro

Tema 7 Máquinas de Turing

Lenguaje aceptado Aceptación de lenguajes La decisión de si una cadena es reconocida por una máquina de Turing depende de si: F ̸= ∅. Decimos que la máquina acepta la cadena por estado de aceptación, si después de una secuencia de movimientos, la máquina de Turing llega a un estado de parada (y por tanto, se para). F = ∅. Diremos que la máquina acepta una cadena por parada si es capaz de parar. Es decir, si una cadena no es reconocida, la máquina entra en un bucle infinito y no para nunca. A diferencia de los AF y AP, una MT no necesita leer toda la cadena para decidir si pertenece o no a un lenguaje

Gabriel Navarro

Tema 7 Máquinas de Turing

Lenguaje aceptado

Lenguaje aceptado La colección de cadenas aceptadas por una máquina de Turing M se llama lenguaje aceptado por la máquina de Turing ℒ(M).

Se dice que un lenguaje L es un lenguaje aceptado por una máquina de Turing si existe un MT M tal que L = ℒ(M).

Gabriel Navarro

Tema 7 Máquinas de Turing

Ejemplos

El lenguaje de las palabras con un número 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 )

Gabriel Navarro

Tema 7 Máquinas de Turing

Ejemplos

El lenguaje de las palabras con un número 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 )

Gabriel Navarro

Tema 7 Máquinas de Turing

Ejemplos

El lenguaje {an bn 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 , B) = (q1 , B, D) f (q2 , B) = (q2 , B, I ) f (q2 , A) = (q0 , A, D) f (q0 , B) = (q3 , B, D) f (q3 , #) = (q4 , #, D)

Gabriel Navarro

f (q1 , a) = (q1 , a, D) f (q1 , b) = (q2 , B, I ) f (q2 , a) = (q2 , a, I ) f (q3 , B) = (q3 , B, D)

Tema 7 Máquinas de Turing

Ejemplos

El lenguaje {an bn 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 , B) = (q1 , B, D) f (q2 , B) = (q2 , B, I ) f (q2 , A) = (q0 , A, D) f (q0 , B) = (q3 , B, D) f (q3 , #) = (q4 , #, D)

Gabriel Navarro

f (q1 , a) = (q1 , a, D) f (q1 , b) = (q2 , B, I ) f (q2 , a) = (q2 , a, I ) f (q3 , B) = (q3 , B, D)

Tema 7 Máquinas de Turing

Ejemplos

El lenguaje {an bn c n con n ≥ 1} {{a, b, c}, {a, b, c, X , Y , Z , #}, {q0 , qa , qb , qc , qY , qZ , qf }, q0 , f , {qf }} f q0 qa qb qc qY qZ

a (qa , X , D) (qa , a, D) − (qc , a, I ) − −

b − (qb , Y , D) (qb , b, D) (qc , b, I ) − −

c − − (qc , Z , I ) − − −

X − − − (q0 , X , D) − −

Y (qY , Y , D) (qa , Y , D) − (qc , Y , I ) (qY , Y , D) −

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

Gabriel Navarro

Tema 7 Máquinas de Turing

Z − − (qb , Z , D) (qc , Z , I ) (qZ , Z , D) (qZ , Z , D)

Ejemplos

El lenguaje {an bn c n con n ≥ 1} {{a, b, c}, {a, b, c, X , Y , Z , #}, {q0 , qa , qb , qc , qY , qZ , qf }, q0 , f , {qf }} f q0 qa qb qc qY qZ

a (qa , X , D) (qa , a, D) − (qc , a, I ) − −

b − (qb , Y , D) (qb , b, D) (qc , b, I ) − −

c − − (qc , Z , I ) − − −

X − − − (q0 , X , D) − −

Y (qY , Y , D) (qa , Y , D) − (qc , Y , I ) (qY , Y , D) −

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

Gabriel Navarro

Tema 7 Máquinas de Turing

Z − − (qb , Z , D) (qc , Z , I ) (qZ , Z , D) (qZ , Z , D)

Lenguajes aceptados por un MT Lenguaje recursivamente enumerable Los lenguajes aceptados por una máquina de Turing se llaman lenguajes recursivamente enumerables Esta es una clase de lenguajes más amplia que los lenguajes independientes de contexto

Reg

Gabriel Navarro

LIC

LRE

Tema 7 Máquinas de Turing

Lenguajes aceptados por un MT Lenguaje recursivo Un lenguaje que es aceptado por una MT de manera que se produce una parada para todas y cada una de las cadenas que se dan como entrada a la máquina, se conocen como lenguajes recursivos. Los lenguajes recursivos también forman una clase mayor que la de los lenguajes independientes del contexto

Reg

Gabriel Navarro

LIC

LR

LRE

Tema 7 Máquinas de Turing

Gramáticas y MT

Teorema Para toda gramática de tipo 0, existe una máquina de Turing que reconoce el lenguaje generado por dicha gramática Teorema Para toda máquina de Turing, existe una gramática de tipo 0 que genera un lenguaje igual al reconocido por la máquina de Turing

Gabriel Navarro

Tema 7 Máquinas de Turing

Autómata lineal acotado Un autómata lineal acotado es una MT cuya cinta es finita, concretamente, Autómata lineal acotado Un ALA es una MT (Σ, Γ, #, Q, q0 , f , F ) donde: Tendrá que realizar su computación únicamente en las celdas ocupadas originariamente por la cadena de entrada, utilizando por consiguiente una cinta de entrada limitada, y no ilimitada como es el caso de la Máquinas de Turing generales Presenta dos símbolos de cinta ⟨ y ⟩ que marcan el principio y final de cinta La máquina no se puede mover a la izquierda de ⟨, ni a la derecha ⟩ Los símbolos ⟨ y ⟩ no pueden ser sobreescritos

Gabriel Navarro

Tema 7 Máquinas de Turing

Autómata lineal acotado Lenguaje aceptado Los lenguajes aceptados por un ALA son los lenguajes dependientes del contexto. Recíprocamente, dado un lenguaje dependiente del contexto existe un ALA que lo acepta

Reg

Gabriel Navarro

LIC

LDC

LR

Tema 7 Máquinas de Turing

LRE

Jerarquía de Chomsky

Lenguaje Regular Libre de Contexto Dependiente del Contexto Recursivo Recursivamente enumerable

Gramática Tipo 3 Tipo 2 Tipo 1 Tipo 0

Gabriel Navarro

Máquina Teórica Autómata Finito Autómata con pila Autómata lineal acotado Máquina de Turing que para Máquina de Turing

Tema 7 Máquinas de Turing

Variaciones de una MT

Con la misma potencia de cálculo Máquina de Turing no determinista Máquina de Turing con cinta infinita sólo a un lado Máquina de Turing multicinta Máquina de Turing multidimensional

Gabriel Navarro

Tema 7 Máquinas de Turing

¿Por qué MT? Límites de cálculo Es un módelo para establecer qué es posible calcular y qué no. Es un modelo de computación Problemas de decisión Es un problema que ante cualesquiera datos de entrada la respuesta es “sí” o “no” No es muy restrictivo Todos los problemas se pueden escribir como un problema de decisión

Gabriel Navarro

Tema 7 Máquinas de Turing

¿Por qué MT? Límites de cálculo Es un módelo para establecer qué es posible calcular y qué no. Es un modelo de computación Problemas de decisión Es un problema que ante cualesquiera datos de entrada la respuesta es “sí” o “no” No es muy restrictivo Todos los problemas se pueden escribir como un problema de decisión

Gabriel Navarro

Tema 7 Máquinas de Turing

¿Por qué MT? Límites de cálculo Es un módelo para establecer qué es posible calcular y qué no. Es un modelo de computación Ejemplo Conjetura de Goldbach: Todo número par mayor que 2 puede escribirse como suma de dos números primos bool Goldbach (int n){ for (int i=2;i<=n;i++) for (int j=2;j<=n;j++) if (PRIMO(i) && PRIMO(j) && i+j==n) return true; return false; } Gabriel Navarro

Tema 7 Máquinas de Turing

¿Por qué MT? Límites de cálculo Es un módelo para establecer qué es posible calcular y qué no. Es un modelo de computación Problemas de decisión En general, un problema de decisión cualquiera se puede representar por un lenguaje Turing-computable Un problema será Turing-computable si su lenguaje es aceptado una MT. Esto es, si es recursivamente enumerable

Gabriel Navarro

Tema 7 Máquinas de Turing

¿Por qué MT?

No es el único modelo de computación 𝜆-cálculo Juego de la vida Funciones recursivas parciales ... aunque las propuestas “serias” son todas equivalentes Tesis de Turing-Church El poder computacional de una máquina de Turing es tan grande como el de cualquier sistema computacional posible (por ejemplo, los ordenadores actuales)

Gabriel Navarro

Tema 7 Máquinas de Turing

¿Por qué MT? Algoritmo Una MT que siempre para es una forma de “definir” la noción de algoritmo Problemas decidibles Un problema que es resuelto por una máquina de Turing que siempre para se llama decidible es decir, su lenguaje asociado es recursivo es decir, existe un algoritmo que lo resuelve

Gabriel Navarro

Tema 7 Máquinas de Turing

¿Por qué MT? Algoritmo Una MT que siempre para es una forma de “definir” la noción de algoritmo Problemas indecidibles Un problema para el que NO existe una máquina de Turing que pare se llama indecidible. Es decir, su lenguaje asociado NO es recursivo

Gabriel Navarro

Tema 7 Máquinas de Turing

¿Por qué MT? Algoritmo Una MT que siempre para es una forma de “definir” la noción de algoritmo Es decir

Problemas

⎧ ⎨

{︂

no Turing-computable (no rec. enum.) Turing-computable ⎩ decidibles (recursivos) indecidibles

Gabriel Navarro

Tema 7 Máquinas de Turing

Lenguajes que no son recursivamente enumerables Pregunta ¿Existen lenguajes que no son recursivamente enumerables? Respuesta El lenguaje diagonal Ld

Gabriel Navarro

Tema 7 Máquinas de Turing

Lenguajes que no son recursivamente enumerables Pregunta ¿Existen lenguajes que no son recursivamente enumerables? Codificación de máquinas de Turing Para una MT, M = ({0, 1}, Q, {0, 1, B}, f , q1 , B, {q2}) (no es restrictivo) 0 = x1 codifica a 0 1 = x2 codifica a 00 B = x3 codifica a 000 qi codifica a 0i D = D1 codifica a 0 I = D2 codifica a 00

Gabriel Navarro

Tema 7 Máquinas de Turing

Lenguajes que no son recursivamente enumerables Pregunta ¿Existen lenguajes que no son recursivamente enumerables? Codificación de máquinas de Turing Para una MT, M = ({0, 1}, Q, {0, 1, B}, f , q1 , B, {q2}) (no es restrictivo) Cada transición se codifica de la manera: f (qi , xj ) = (qk , xl , Dm ) → 0i 10j 10k 10l 10m La máquina M se codifica a 111Transicion1 11Transicion2 11Transicion3 ....Transicionn 111

Gabriel Navarro

Tema 7 Máquinas de Turing

Lenguajes que no son recursivamente enumerables Pregunta ¿Existen lenguajes que no son recursivamente enumerables? Codificación de máquinas de Turing Por 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 1110100100010100110001010100100110 0010010010100110001000100010010111 De esta manera, cada MT es un número entero en binario Gabriel Navarro

Tema 7 Máquinas de Turing

Lenguajes que no son recursivamente enumerables Pregunta ¿Existen lenguajes que no son recursivamente enumerables? Construcción de Ld Se 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 aceptada por j y 0, si no lo es 1 2 3 1 0 1 1 2 1 0 1 3 1 1 1 .. .. .. .. . . . . Gabriel Navarro

4 0 1 0 .. .

··· ··· ··· ··· .. .

Tema 7 Máquinas de Turing

Lenguajes que no son recursivamente enumerables Pregunta ¿Existen lenguajes que no son recursivamente enumerables? Construcción de Ld Ld está formado por las cadenas i que no son reconocidas por la MT i, es decir, las cadenas cuya fila tiene en la diagonal un cero 1 2 3 4 ··· 1 0 1 1 0 ··· 2 1 0 1 1 ··· 3 1 1 1 0 ··· .. .. .. .. .. . . . . . . . .

Gabriel Navarro

Tema 7 Máquinas de Turing

Lenguajes que no son recursivamente enumerables Pregunta ¿Existen lenguajes que no son recursivamente enumerables? Ld no es recursivamente enumerable Si lo fuera, entonces Ld es reconocido por la MT j-ésima, para cierto 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 es recursivamente enumerable

Gabriel Navarro

Tema 7 Máquinas de Turing

Lenguajes recursivamente enumerables

Pregunta ¿Existen lenguajes recursivamente enumerables que no son recursivos? Esto es, ¿existen problemas para los que no hay un algoritmo que los resuelva pero que son Turing-computables? Problema de la parada Sea M una máquina de Turing y una cadena w , ¿para M con entrada w ?

Gabriel Navarro

Tema 7 Máquinas de Turing

Lenguajes recursivamente enumerables Problema de la parada Sea M una máquina de Turing y una cadena w , ¿para M con entrada w ? No es decidible Si existiese un algoritmo bool PARA(M,w) donde: M es la codificación de la MT w la cadena puedo construir bool Diagonal (M){ if (PARA(M,M)) while (1){} else return 1; } Gabriel Navarro

Tema 7 Máquinas de Turing

Lenguajes recursivamente enumerables Problema de la parada Sea M una máquina de Turing y una cadena w , ¿para M con entrada w ? No es decidible Esto es, Diagonal(M) termina si y sólo si M(M) nunca termina Si usamos M=Diagonal Diagonal(Diagonal) termina si y sólo 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 Gabriel Navarro

Tema 7 Máquinas de Turing

Lenguajes recursivamente enumerables

Otro ejemplo (Hopcroft-Motwani-Ullman, Introduction to...) Usando la codificación de máquinas de Turing: Le = {M máquina de Turing tal que ℒ(M) = ∅} Lne = {M máquina de Turing tal que ℒ(M) ̸= ∅} se tiene que: Le no es recursivamente enumerable Lne es recursivamente enumerable no recursivo ...sin embargo, uno es el complementario de otro...

Gabriel Navarro

Tema 7 Máquinas de Turing

Problemas indecidibles

Algunos problemas indecidibles Comprobar, si dos LIC son el mismo lenguaje si una LIC es un lenguaje regular si un LIC es inherentemente ambiguo si una GIC es ambigua si la intersección de dos LIC es el vacío si el lenguaje aceptado por una MT es vacío

Gabriel Navarro

Tema 7 Máquinas de Turing

Problemas indecidibles

Otros problemas indecidibles 10o problema de Hilbert El problema de la Correspondencia de Post Hilbert Entscheidungsproblem The mortal matrix problem

Gabriel Navarro

Tema 7 Máquinas de Turing

Problemas tratables e intratables

Aunque un problema sea decidible, puede que el cálculo del algoritmo que lo resuelve no se obtenga en un tiempo “razonable” Tiempo de ejecución Llamamos tiempo de ejecución T (M, w ) de una MT M para la entrada w , al número de pasos que M ejecuta antes de pararse Función de ejecución La función de ejecución de un MT M, T : N → N, se define por T (n) = max{T (M, w ) con |w | = n}

Gabriel Navarro

Tema 7 Máquinas de Turing

Problemas tratables e intratables

Aunque un problema sea decidible, puede que el cálculo del algoritmo que lo resuelve no se obtenga en un tiempo “razonable” Problema tratable Un problema decidible es tratable si es resuelto por una MT con tiempo de ejecución polinomial Problema intratable Un problema decidible es intratable si no es tratable

Gabriel Navarro

Tema 7 Máquinas de Turing

𝒫 = 𝒩𝒫

La clase 𝒫 Un problema decidible está en la clase 𝒫 si es resuelto por un MT determinista en tiempo polinomial La clase 𝒩 𝒫 Un problema decidible está en la clase 𝒩 𝒫 si es resuelto por un MT no determinista en tiempo polinomial

Gabriel Navarro

Tema 7 Máquinas de Turing

𝒫 = 𝒩𝒫

Es obvio que 𝒫 ⊆ 𝒩 𝒫 Problema del milenio (1000000 $, Clay Mathematics Institute) ¿𝒫 = 𝒩 𝒫?

Gabriel Navarro

Tema 7 Máquinas de Turing