Máquinas de Turing (MT)
(O cómo hacer más que simplemente
recordar)
Recordatorio
• Examen final
– Sábado 15 de mayo de 2004 a las 08:00 hrs en
el auditorio 5 (de prepa)
Autómatas son insuficientes
• Autómatas finitos modelan adecuadamente
mecanismos que requieren una memoria “pequeña”.
• Autómatas de pila modelan adecuadamente
mecanismos que requieren memoria infinita que sólo
puede ser replicada con una pila LIFO (Last In First
Out)
• {anbncn | n > 0} no es un lenguaje libre de contexto
pero sí es sensitivo al contexto, es decir, es generado
por una gramática sensitiva al contexto.
• {anbncn | n  0} no es un lenguaje sensitivo al contexto
(porque contiene ) pero sí es un lenguaje
recursivamente numerable, es decir, es generado por
una gramática sin restricción.
{anbncn | n > 0} es un lenguaje
sensitivo al contexto
1. S  aBTc | abc
2. T  ABTc
3. T  ABc
4. BA  BX
5. BX  YX
6. YX  AX
7. AX  AB
8. aA  aa
9. aB  ab
10. bB  bb
• Las reglas 1 a 3 generan el
número correcto de a’s,
b’s y c’s (contando
mayúsculas y minúsculas).
• Las reglas 4 a 7 ordenan
las letras (mayúsculas y
minúsculas) en el orden
correcto.
• Las reglas 8 a 10 generan
los símbolos terminales
sólo cuando están en el
orden correcto.
{anbncn | n  0} es un lenguaje
recursivamente numerable
1. S  aBTc | abc | 
2. T  ABTc
3. T  ABc
4. BA  BX
5. BX  YX
6. YX  AX
7. AX  AB
8. aA  aa
9. aB  ab
10. bB  bb
• Las reglas 1 a 3 generan el
número correcto de a’s,
b’s y c’s (contando
mayúsculas y minúsculas).
• Las reglas 4 a 7 ordenan
las letras (mayúsculas y
minúsculas) en el orden
correcto.
• Las reglas 8 a 10 generan
los símbolos terminales
sólo cuando están en el
orden correcto.
Lema de bombeo para LLC
• Si L es un lenguaje libre de contexto, entonces
existe un número n (la longitud de bombeo) tal que
si w es cualquier cadena en L de longitud mayor o
igual que n, entonces w puede ser dividido en cinco
partes, w = uvxyz, que satisfacen las siguientes tres
condiciones:
– 1) uvixyiz  L para toda i  0.
– 2) |vy| > 0.
– 3) |vxy| ≤ n.
Lenguajes sensitivos al contexto
LR
{anbn}
Xa
LLC
nbncn}
{a
LSC
a X b a g b
Ejemplos de LLC cuya intersección
no es un LLC
• L1 = {aibjck | i < j} es LLC porque la siguiente
gramática libre de contexto lo genera:
– S  ABC, A  aAb | , B  bB | b, C  cC | 
• L2 = {aibjck | i < k} es LLC porque la siguiente
gramática libre de contexto lo genera:
– S  AC, A  aAc | B, B  bB | , C  cC | c
• Sin embargo L = L1 ∩ L2 no es LLC.
Ejemplo de un LLC cuyo
complemento no es LLC
• L = {aibjck | ¬(i = j = k)} es LLC porque es
la unión de
– L1 = {aibjck | i  j}
– L2 = {aibjck | j  k}
• Sin embargo el lenguaje LC = {aibici | i  0}
no es LLC.
Máquinas de Turing
• Máquina abstracta definida por el matemático inglés Alan Turing
en Proceedings of the London Mathematical Society 2:230-265,
1936.
• Turing empezó tratando de modelar a una computadora humana, es
decir, a un humano tratando de resolver algoritmicamente un
problema utilizando papel y lápiz.
– Reglas básicas
• Sólo se pueden escribir símbolos que pertenecen a un conjunto finito.
• Cada acción que la computadora toma sólo depende del símbolo que está siendo
examinado y del “estado mental” en ese momento.
• Aunque el estado mental puede cambiar como resultado de los símbolos o
cálculos que se han efectuado, el número de estados mentales distintos es finito.
• Máquina abstracta
– Examinar un símbolo individual en el papel.
– Borrar un símbolo o reemplazarlo por otro.
– Trasladar la atención de una parte del papel a otra.
Máquinas de Turing
• Se tiene un alfabeto de entrada y un alfabeto,
posiblemente mayor, de los símbolos utilizados
durante la operación o cálculos de la máquina.
• Un conjunto finito de estados que representan los
distintos “estados mentales”.
• En lugar de una hoja de papel, se tiene una cinta
linear semi-infinita con inicio en el extremo
izquierdo e infinita hacia la derecha. Esta cinta
esta dividida en cuadros, en cada uno de los cuales
puede estar un símbolo o un espacio en blanco (#).
Caricatura de una MT
Operación de la MT
• La acción está determinada por el estado actual y el símbolo en la
cinta y consiste de tres partes
– Reemplazar el símbolo en el cuadrado actual por otro que puede ser distinto o el
mismo.
– Mover la cabeza lectora a la derecha o a la izquierda (a menos que se encuentre
en el extremo izquierdo de la cinta) o quedarse donde está.
– Hacer una transición de estado, que puede ser distinto o el mismo.
• La cinta sirve como dispositivo de entrada y salida así como la
memoria disponible para utilizar durante la operación o cálculos de la
máquina.
• Diferencias de una MT con un autómata
– La cabeza lectora se puede mover a la izquierda o derecha o quedarse donde
está.
– Puede modificar los datos de entrada.
– Puede examinar parte de los datos de entrada, modificarlos, irse a otro lugar de
la cinta y ejecutar ciertos cálculos, regresar a re-examinar los datos de entrada,
repetir cualquiera de estas acciones y quizás detener el proceso antes de procesar
todos los datos de entrada.
– En lugar de que un subconjunto de los estados sean estados finales o de
aceptación, tendremos dos estados de paro que son un estado de aceptación ha y
un estado de rechazo hr.
Definición formal de Máquina de Turing
• Una Máquina de Turing es un quinteto
T = (Q, , , q0, )
– Q es un conjunto finito de estados en el que no está incluído los
estados de paro ha y hr.
–  es el alfabeto de entrada con el que se forman las cadenas a
procesar.
–  es el alfabeto de la cinta que contiene a  pero no al espacio en
blanco (#).
– q0 es el estado inicial y pertenece a Q.
– La función de transición
: Q  (  {#})  Q  {ha, hr}  (  {#}) {#})  {R, L, S}
(q, X) = (r, Y, D) significa que si la máquina se encuentra en el
estado q y leyendo el símbolo X en la cinta, entonces la máquina
reemplaza X por Y, se mueve al estado r y mueve la cabeza
lectora en la dirección D.
Notación gráfica
• (q, X) = (r, Y, D) se puede representar
gráficamente de la siguiente manera
X/Y, D
q
r
Configuración inicial
# a
b b a
# # # … ...
Aceptación de palabras por MT
• Una palabra x  * es aceptada por una MT
T si empezando con la configuración inicial
correspondiente a la palabra x,
eventualmente se llega al estado de
aceptación ha.
Note que no es necesario procesar toda la
palabra para aceptarla.
El lenguaje aceptado por T es el conjunto
de palabras aceptadas por T.
Rechazo de palabras por MT
• Una palabra x  * es rechazada por una MT T si
empezando con la configuración inicial
correspondiente a la palabra x, eventualmente se
llega al estado de rechazo hr.
Note que no es necesario procesar toda la palabra
para rechazarla.
Es costumbre omitir el estado de rechazo y
rechazar una palabra cuando no existe una
transición, es decir, cuando la máquina se queda
“colgada”.
Ejemplo
MT que acepta palabras sobre {a, b} que
inician con ‘a’
1
#/#,R
2
a/a,S
b/b,S
#/#,S
hr
ha
Ejemplo: MT palabras en {a, b}
que terminan con ‘a’
a/a,R
b/b,R
1
#/#,R
2
#/#,L
3
a/a,S
b/b,S
#/#,S
hr
ha
EjemplosMT que acepta
(a + b)*aba(a + b)*
• MT que acepta (a + b)*aba(a + b)*
• MT que acepta (a + b)*aba
• MT que acepta palindromos sobre {a, b}.
(a + b)*aba(a + b)*
(a + b)*aba
Palíndromos sobre {a, b}
L = {ss | s  (a + b)*}
Este lenguaje no es libre de contexto
Estatus de una MT. Versión 1
• La configuración de una Máquina de Turing está definida por a) el
estado en el que se encuentra, b) el contenido de la cinta y c) la
posición de la cabeza lectora. La configuración se representa como uqv
cuando la MT se encuentra en el estado q, el contenido de la cinta es la
cadena uv (en ese orden, de izquierda a derecha) y la cabeza lectora se
encuentra en el primer símbolo de v. La cinta sólo contiene espacios
blancos (#) a la derecha del último símbolo de v; para abreviar, estos
blancos a la derecha de la palabra no se indican en la configuración .
Por ejemplo, #1011q701111 representa la configuración cuando el
contenido de la cinta es #101101111###..., el estado es q7 y la cabeza
lectora se encuentra sobre el segundo ‘0’.
#
1
0
1
1
0
1
1
1
1
#
#
#
...
q7
Estatus de una MT. Versión 2
(Texto de John Martin)
• La configuración de una Máquina de Turing se representa por una
pareja ordenada (q, xay) que indica que la MT se encuentra en el
estado q, el contenido de la cinta es xay y la cabeza lectora se
encuentra en el símbolo subrayado. En xay se incluye sólo hasta el
último símbolo a la derecha diferente del espacio en blanco
representado por # ó por .
• La siguiente configuración se representa por
(q7,, #101101111).
#
1
0
1
1
0
1
1
1
1
#
#
#
...
q7
Aceptabilidad
• Decimos que un lenguaje L es Turingaceptable si existe una máquina de Turing
que dá halt para toda entrada w  L, es
decir, la palabra w es aceptada por la
máquina de Turing.
Ejemplo
• Máquina de Turing que acepte el lenguaje L = {1x | x = 2n
para n  0}, es decir, cadenas de 1’s cuya longitud es una
potencia de 2.
Idea de construcción:
– 1) Barrer la palabra de izquierda a derecha “tachando” un 1 sí y
otro no.
– 2) Si en el paso 1) la cinta contiene sólo un 1, entonces parar y
aceptar.
– 3) Si en el paso 1) la cinta contiene más de un 1 y el número de
1’s es impar, entonces rechazar.
– 4) Regresar la cabeza lectora al extremo izquierdo de la cinta.
– 5) Ir al paso 1).
1/1,L
x/1,L
x/x,R
1/#,L
#/#,L
1/x,R
#/#,R
#/#,R
#/#,L
1/x,R
1/1,R
#/#,S
ha
1/1,R
Tarea 5. Segunda parte
Fecha límite de entrega: 15/Mayo/2004
• Ilustrar que la MT de la lámina anterior
acepta el lenguaje {1x | x = 2n para n  0}.
Para esto, analizar el comportamiento para las
siguientes cadenas: 1, 11, 111, 1111, 11111,
111111, 11111111.
• Construir una máquina de Turing que acepte
el lenguaje {anbncn | n  0}.
La primera parte de esta Tarea 5 está en la
última lámina del TLarchivo08.ppt
Tesis de Church y límites de MT
O cuando aún lo mejor no es
suficiente…
Aceptar vs. decidir
• 1.- Todo lenguaje T-decidible es Taceptable.
• 2.- L es T-decidible ssi Lc es T-decidible.
• 3.- L es T-decidible ssi tanto L como Lc son
T-aceptables.
Propuesta de A. Church
• No hay ningún tipo de máquina abstracta
más poderosa que la MT (es decir, que
acepte / decida clases de lenguajes más
grandes).
• La “tesis” de Church no ha sido ni probada
ni refutada.
Se ha comparado MT con:
• Extensiones de la misma MT:
– Cinta infinita a la izquierda
– No determinismo
– Varias cintas, varias cabezas
• Otras máquinas:
– Máquinas de Post
– Autómatas de varias pilas
• Otros paradigmas: cálculo lambda
Cinta infinita a la izquierda
Máquinas de Post
Límites de las MT
• Problema del paro (“halt”) de una MT con
una palabra w.
• El lenguaje indecidible en este caso es el
formado por palabras d(M)w en que M da
halt con la entrada w.
…Pero no se puede…
• Teorema: No existe ninguna MT que decida
el lenguaje formado por palabras d(M)w en
que M da halt con la entrada w.
Prueba por contradicción
Suponemos una MT llamada A:
Modificamos A, dando B:
Alimentamos B con d(B):
¡Contradicción!
Formalmente…
Fin de “ejecución”
• “Estado” de paro (“halt”)
– detiene la operación.
– acepta la palabra.
• Ciclo infinito o colgar la máquina
– ejecución nunca termina o no puede continuar.
– la palabra es rechazada.
• Un lenguaje para el que existe una Máquina de
Turing que lo acepte se dice que es un lenguaje
recursivamente numerable.
Descargar

Máquina de Turing