Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de...
Transcript of Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de...
![Page 1: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/1.jpg)
1
Lenguajes
decidibles
y semidecidibles
Elvira Mayordomo, Universidad de Zaragoza
![Page 2: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/2.jpg)
2
Programas
…•Consideramos
programas
sintácticamente
correctos
…
•El único
añadido
es
que
la memoria es ilimitada
(es decir no hay nunca errores por
“overflow”)
Luego
si
probamos
que
algo
no se puederesolver con ningún
programa
es
un resultado
muy
general …
![Page 3: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/3.jpg)
3
Nos
interesan
especialmente
tipo tpresultado = (acepta,rechaza)
procedimiento ejemplo (ent w:cadena; sal z:tpresultado)
![Page 4: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/4.jpg)
4
Aceptar
Aceptar
Entrada Si el programa
paray devuelve
acepta
Rechazar
Entrada
Si el programa
paray no devuelve
acepta
oSi el programa
no para
nunca
![Page 5: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/5.jpg)
5
El lenguaje
aceptado
Para un programa p
devuelvey para
entradacon programa el:)(
acepta
wpwpL
Definición: Un lenguaje
es
semidecidible
si
es
el
aceptado
por
un programa
![Page 6: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/6.jpg)
6
Programas
que
paran
siempre
Una programa p para
siempre
si
para cualquier
cadena
w, p con entrada
w
para
![Page 7: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/7.jpg)
7
Lenguajes
decidibles
Definición: Un lenguaje
L es
decidible
si
es
el aceptado
por
un programa
que
para
siempre
Lw p para
y devuelve
acepta
Lw p para
y no devuelve
acepta
![Page 8: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/8.jpg)
8
Lenguajes
decidiblesUn lenguaje
L es
decidible
si
es
el aceptado
por
un programa
que
para
siempre
En otras
palabras:Un lenguaje
L es
decidible
si
existe
un
algoritmo
que
resuelve
completamente
el problema
de pertenencia
a L
![Page 9: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/9.jpg)
9
*aLenguajes
regulares
Lengs. indeps. del contextonnba Rww
nnn cba ww
**ba
Lenguajes
semidecidibles(aceptados
por
programas)
![Page 10: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/10.jpg)
10
Resultado
elemental
Todo
lenguaje
decidible
es
semidecidible
Demostración.
Mirar
las
definiciones.
![Page 11: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/11.jpg)
11
*aLenguajes
regulares
Lengs. indeps. del contextonnba Rww
nnn cba ww
**ba
Lenguajes
semidecidibles
Lenguajes
decidibles
![Page 12: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/12.jpg)
12
??¿Hay lenguajes
no semidecidibles?
Veremos
que
sí
utilizando
la famosa
técnica de diagonalización
![Page 13: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/13.jpg)
13
El problema
de parada
![Page 14: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/14.jpg)
14
El problema
de parada
Dado un programa
p y una
cadena
w
¿p con entrada
w para?
![Page 15: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/15.jpg)
15
El problema
de parada
H= { (p , w) : p es
un programa
que
para
con entrada
w}
Cada
programa
es
una
cadena, y codificamos (p,w) como
p#w
![Page 16: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/16.jpg)
16
Simulando
máquinas
de TuringPodemos
simular
una
máquina
M con entrada
w durante
T pasos
Procedimiento
SimulaMT
(ent
M:cadena; ent w:cadena; ent
T:natural; sal
ha_parado:booleano;
sal
resultado:tpresultado)
{Simula
T pasos
de la ejecución
de M con entrada
w}{ha_parado=True cuando
ha parado
en tiempo<=T}
{resultado=acepta
si
ha parado
en estado
final}
![Page 17: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/17.jpg)
17
Simulando
máquinas
de TuringProcedimiento
SimulaMT
(ent
M:cadena; ent
w:cadena; ent
T:natural; sal
ha_parado:booleano; sal
resultado:tpresultado)
Variables ...{Simula
T pasos
de la ejecución
de M con entrada
w}
principioha_parado:= Falsetiempo:=0entrada:= concatena(“$”,w) {seguido
de blancos}
memoria:= …
{$ seguido
de blancos}cabeza_ent:=2; cabeza_mem:=2q:=q0; a:=w(1); b:=blanco
![Page 18: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/18.jpg)
18
Simulando
máquinas
de TuringMientrasQue
(Not ha_parado) AND (tiempo<T)
hacerSi “hay una
transición”
desde
(q,a,b)
“seguirla”
{ aplicar
transición
actualizando
q,a,by cabezas
}
tiempo:=tiempo+1sino
ha_parado:= True
FsiFmqSi esFinal(q) entonces
resultado:= acepta
sino
resultado:=rechaza; Fsifin
![Page 19: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/19.jpg)
19
Simulando
programasPodemos
simular
un programa
p con entrada
w
durante
T pasos
(como
hacen
los intérpretes
o los debuggers)
Procedimiento
Simula
(ent
p:cadena; ent
w:cadena; ent
T:natural; sal
ha_parado:booleano;
sal
resultado:tpresultado)
{Simula
T pasos
de la ejecución
de p con entrada
w}{ha_parado=True cuando
ha parado
en tiempo<=T}
{resultado=acepta
si
ha parado
y devuelve
acepta}
![Page 20: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/20.jpg)
20
Teorema
H es
semidecidible
H= { (p , w) : p es
un programa
que
para
con entrada
w}
![Page 21: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/21.jpg)
21
H es
semidecidibleH= { (p , w) : p es
un programa
que
para
con entrada
w}
Procedimiento
aceptaH(ent
p:cadena; ent
w:cadena; sal
z:tpresultado)
Variable res:tpresultadoPrincipio
T:=1; ha_parado:=falseMientrasQue
NOT ha_parado
simula(p,w,T,ha_parado,res)T:=T+1
FmqSi ha_parado
entonces
z:=acepta
Fin
![Page 22: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/22.jpg)
22
H es
semidecidible
Si (p,w)H
el programa
aceptaH
acepta
(p,w)
Si (p,w)H
el programa
aceptaH
con entrada (p,w) se cuelga
!!!
![Page 23: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/23.jpg)
23
??¿Hay lenguajes
no semidecidibles?
Veremos
que
sí
utilizando
la famosa
técnica de diagonalización
![Page 24: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/24.jpg)
24
Diagonalización
![Page 25: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/25.jpg)
25
Diagonalizar
una
tablab1
b2
b3
b4
b5
b6
b7
b8
R1
0 1 1 0 0 1 0 1R2
1 1 1 0 0 1 0 0
R3
0 0 0 1 1 1 0 1R4
0 1 0 1 0 1 0 1
R5
1 1 1 0 1 1 0 0R6
1 0 1 0 1 1 0 1
R7
1 0 0 1 1 1 0 1R8
0 0 1 1 1 1 0 1
¿Cómo encontrar una fila distinta a todas?
![Page 26: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/26.jpg)
26
Diagonalizar
una
tablab1
b2
b3
b4
b5
b6
b7
b8
R1
0 1 1 0 0 1 0 1R2
1 1 1 0 0 1 0 0
R3
0 0 0 1 1 1 0 1R4
0 1 0 1 0 1 0 1
R5
1 1 1 0 1 1 0 0R6
1 0 1 0 1 1 0 1
R7
1 0 0 1 1 1 0 1R8
0 0 1 1 1 1 0 11 0 1 0 0 0 1 0
![Page 27: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/27.jpg)
27
Un problema
semidecidible
…
A= { p : p es
un programa
que
acepta
la entrada
p}
![Page 28: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/28.jpg)
28
A es
semidecidible
Procedimiento
aceptaA(ent
p:cadena; sal
z:tpresultado)
PrincipioT:=1; ha_parado:=falseMientrasQue
NOT ha_parado
simula(p,p,T,ha_parado,z)T:=T+1
FmqFin
![Page 29: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/29.jpg)
29
El complementario
de A
A= { p : p es
un programa
que
NO acepta
la entrada
p}
Vamos
a ver
que
A no es
semidecidible
usandodiagonalización
![Page 30: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/30.jpg)
30
Diagonalizar
una
tablab1
b2
b3
b4
b5
b6
b7
b8
R1
0 1 1 0 0 1 0 1R2
1 1 1 0 0 1 0 0
R3
0 0 0 1 1 1 0 1R4
0 1 0 1 0 1 0 1
R5
1 1 1 0 1 1 0 0R6
1 0 1 0 1 1 0 1
R7
1 0 0 1 1 1 0 1R8
0 0 1 1 1 1 0 11 0 1 0 0 0 1 0
![Page 31: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/31.jpg)
31
Teorema: A no es
semidecidibleDemostración:
Sea la siguiente
tabla
(infinita): para
cada programa
p hay una
fila, y para
cada
programa
p hay una
columna
El la posición
p,q
escribimos
1 si
el programa p acepta
q y escribimos
0 si
no
![Page 32: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/32.jpg)
32
Demostraciónp1
p2
p3
p4
p5
p6
p7
p8
p1
0 1 1 0 0 1 0 1p2
1 1 1 0 0 1 0 0
p3
0 0 0 1 1 1 0 1p4
0 1 0 1 0 1 0 1
p5
1 1 1 0 1 1 0 0p6
1 0 1 0 1 1 0 1
p7
1 0 0 1 1 1 0 1p8
0 0 1 1 1 1 0 1
¿Qué
es
la diagonal?
![Page 33: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/33.jpg)
33
DemostraciónEn la diagonal hay 1 si
p acepta
p y 0 si
no
Esto
es
1 si
pA y 0 si pA
¿Qué
pasa
si
diagonalizamos?
![Page 34: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/34.jpg)
34
DemostraciónEn la diagonal hay 1 si
p acepta
p y 0 si
no
Esto
es
1 si
pA y 0 si pA
¿Qué
pasa
si
diagonalizamos?
•
Obtenemos
una
fila
que
no está
en la tabla•
Obtenemos
el complementario
de la
diagonal (1 si
pA y 0 si pA)
![Page 35: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/35.jpg)
35
DemostraciónSi hay un programa
Q que
acepte
A, tenemos
que
la fila
de Q en la tabla
tiene1 si
pA y 0 si pA
Pero
eso
es
imposible
porque
hemos
visto
que una
fila
así
no está
en la tabla
(es
el
complementario
de la diagonal)
Luego
no hay un programa
que
acepte
A
Fin de la demostración
![Page 36: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/36.jpg)
36
Ya
tenemos
un primer ejemplo
de lenguaje
no semidecidible:
A= { p : p es
un programa
que
NO acepta
la entrada
p}
Veamos
un segundo
…
![Page 37: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/37.jpg)
37
El problema
diagonal de parada
K= { p : p es
un programa
que
para
con entrada
p}
H= { (p , w) : p es
un programa
que
para
con entrada
w}
pK
si
y sólo
si
(p,p)H
![Page 38: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/38.jpg)
38
K es
semidecidible
pK
si
y sólo
si
(p,p)H
Procedimiento
aceptaK(ent
p:cadena; sal
z:tpresultado)
PrincipioaceptaH(p,p,z)
Fin
![Page 39: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/39.jpg)
39
El complementario
de K
K= { p : p es
un programa
que
NO para
con entrada
p}
Vamos
a ver
que
K no es
semidecidible
usandodiagonalización
![Page 40: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/40.jpg)
40
Diagonalizar
una
tablab1
b2
b3
b4
b5
b6
b7
b8
R1
0 1 1 0 0 1 0 1R2
1 1 1 0 0 1 0 0
R3
0 0 0 1 1 1 0 1R4
0 1 0 1 0 1 0 1
R5
1 1 1 0 1 1 0 0R6
1 0 1 0 1 1 0 1
R7
1 0 0 1 1 1 0 1R8
0 0 1 1 1 1 0 11 0 1 0 0 0 1 0
![Page 41: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/41.jpg)
41
Teorema: K no es
semidecidibleDemostración:
Sea la siguiente
tabla
(infinita): para
cada programa
p hay una
fila, y para
cada
programa
p hay una
columna
El la posición
p,q
escribimos
1 si
el programa p para
con entrada
q
y escribimos
0 si
no
![Page 42: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/42.jpg)
42
Demostraciónp1
p2
p3
p4
p5
p6
p7
p8
p1
0 1 1 0 0 1 0 1p2
1 1 1 0 0 1 0 0
p3
0 0 0 1 1 1 0 1p4
0 1 0 1 0 1 0 1
p5
1 1 1 0 1 1 0 0p6
1 0 1 0 1 1 0 1
p7
1 0 0 1 1 1 0 1p8
0 0 1 1 1 1 0 1
¿Qué
es
la diagonal?
![Page 43: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/43.jpg)
43
DemostraciónEn la diagonal hay 1 si
p para
con entrada
p y
0 si
no
Esto
es
1 si
pK y 0 si pK
¿Qué
pasa
si
diagonalizamos?
![Page 44: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/44.jpg)
44
DemostraciónEn la diagonal hay 1 si
p para
con entrada
p y
0 si
no
Esto
es
1 si
pK y 0 si pK
¿Qué
pasa
si
diagonalizamos?
•
Obtenemos
una
fila
que
no está
en la tabla•
Obtenemos
el complementario
de la
diagonal
![Page 45: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/45.jpg)
45
DemostraciónSi hay un programa
Q que
acepte
K, tenemos
que
la fila
de Q en la tabla
tiene1 si
pK y 0 si pK
Pero
eso
es
imposible
porque
hemos
visto
que una
fila
así
no está
en la tabla
(es
el
complementario
de la diagonal)
Luego
no hay un programa
que
acepte
K
Fin de la demostración
![Page 46: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/46.jpg)
46
Un tercer
ejemplo
de no semidecidible
H= { (p , w) : p es
un programa
que
NO para con entrada
w}
Lo vamos
a ver
usando
que
K no es semidecidible
K= { p : p es
un programa
que
NO para
con entrada
p}
![Page 47: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/47.jpg)
47
Demostración
de que
H no es
semidecidibleReducción
al absurdo
Si H es
semidecidible
tenemos
un programa
R que
acepta
H
Lo podemos
usar
para
aceptar
K: Procedimiento
imposible
(ent
p:cadena;
sal
z:tpresultado)Principio
R(p,p,z)Fin
Fin de la demostración
![Page 48: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/48.jpg)
48
Semidecidibles
no decidibles
![Page 49: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/49.jpg)
49
??
¿Hay lenguajes
semidecidibles
pero
no decidibles?
Es decir
…
¿existe
un lenguaje
aceptado
por
un programa
pero
no por
un programa
que
para
siempre?
![Page 50: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/50.jpg)
50
Por otro lado …Para cualquier
aplicación
práctica
sólo
nos
interesan
los programas
que
paran
siempre
Resolver un problema
es
encontrar
un programa
que
lo resuelva
y pare siempre
Los decidibles
son los que
podemos
resolver
¿Hay no decidibles
interesantes?No decidible
= Indecidible
![Page 51: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/51.jpg)
51
??
¿Hay lenguajes
semidecidibles
perono decidibles?
Es decir
…
¿existe
un lenguaje
aceptado
por
un programa
pero
no por
un programa
que
para
siempre?
![Page 52: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/52.jpg)
52
TeoremaH no es
decidible
DemostraciónLo veremos
en problemas:
•
Como H no es
semidecidible
entonces
H no es
decidible
![Page 53: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/53.jpg)
53
Indecidibles
famosos
no decidibles
![Page 54: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/54.jpg)
54
RecordadResolver un problema
es
encontrar
un
programa
que
lo resuelva
y pare siempre
Un indecidible
es
un problema
que
no podemos
resolver con ningún
algoritmo
![Page 55: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/55.jpg)
55
Indecidible
ya
visto
El problema
de parada
Dado un programa
p y una
cadena
w
¿p con entrada
w para?
![Page 56: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/56.jpg)
56
Casi
visto
El problema
de pertenencia
Dado un programa
p y una
cadena
w
¿p acepta
w?
![Page 57: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/57.jpg)
57
Otro
problema
indecidible
El problema
de parada
para
MT
Dada una
máquina
de Turing M y una
cadena
w
¿La máquina
M con entrada
w para?
![Page 58: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/58.jpg)
58
Otro
problema
indecidible
La detección
de virus
Dado un programa
p
¿Es p un virus?
Un virus es
un programa
que
puede
infectar
otros
programasmodificándolos
incluyendo
una
copia
(que
puede
estar
modificada) de sí
mismo
![Page 59: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/59.jpg)
59
Unos
cuantos
más
•
Dados dos programas, ¿calculan lo mismo?•
Dado un programa p, ¿p para con alguna entrada?
![Page 60: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/60.jpg)
60
Algunos
problemas
indecidibles
sobregramáticas:
• Dada una
gramática
independiente
decontexo
G, ¿es
G ambigua?
• Dadas
gramáticas
independientes
decontexo, ¿
? )()( 21 GLGL
21,GG
![Page 61: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/61.jpg)
61
Y otro: Wang tiles
Dado un conjunto finito de baldosas, con un color en cada lado
Ejemplo:
¿puede embaldosarse con ellos el plano, de forma que los lados contiguos tengan el mismo color?
(se pueden hacer tantas copias como se quiera, no se pueden girar ni invertir)
![Page 62: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/62.jpg)
62
Wang tiles
Ejemplos fáciles: periódicos
Datos:
Embaldosadoampliable:
![Page 63: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/63.jpg)
63
Wang tiles
Ejemplos fáciles:
Datos:
Respuesta: No se puede embaldosar el plano
![Page 64: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/64.jpg)
64
Wang tiles
Ejemplos difíciles: aperiódicos
Datos:
Respuesta: Se puede embaldosar el plano de forma no periódica (Ejercicio: intentarlo)
Muy aplicados para construir imágenes y texturas
![Page 65: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/65.jpg)
65
Wang tiles
El problema es indecidible: no hay un algoritmo que lo resuelva
Al principio Wang presentó
un algoritmo que lo resuelve pero suponiendo que todos los embaldosados son periódicos (falso)
![Page 66: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/66.jpg)
66
Y otro másEl problema de correspondencia de Post
Dadas dos listas de palabras x1
, x2
, …, xk
y1
, y2
, …, yk
¿existen
a1, a2, …, an para
los cualesxa1
xa2
…xan
= ya1
ya2
…yan
?
![Page 67: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/67.jpg)
67
El problema de PostEjemplo: u1
=aba u2
= bbb u3
=aab u4
=bb,v1
=a v2
=aaa v3
=abab v4
=babba
aba
a
bbb
aaa
aab
abab
bb
babba
aba
a
aba
a
bb
babba
aab
abab
Datos:
![Page 68: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/68.jpg)
68
El problema de PostEjemplo:
abb
a
bb
aaa
abb
ababDatos:
Respuesta: No
![Page 69: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/69.jpg)
69
El problema de PostEjemplo:
I
PPI
IPP
I
IS
I
M
MDatos:
S
SS
M
M
IS
I
S
SS
IS
I
IPP
I
I
PPI
![Page 70: Elvira Mayordomo, Universidad de Zaragozawebdiis.unizar.es/asignaturas/TC/wp/wp-content/... · de diagonalización. 13. El problema de parada. 14. El problema de parada. Dado un programa](https://reader036.fdocumento.com/reader036/viewer/2022071011/5fc9cf7b91d6d5626a17323b/html5/thumbnails/70.jpg)
70
Uno de matemáticasEl décimo problema de Hilbert
Dada una ecuación con coeficientes enteros, ¿existe una solución entera?
Ejemplos: x2+y2=132x-11=0