Download - Lógica y computabilidad
-
7/25/2019 Lgica y computabilidad
1/66
Logica y Computabilidad
Santiago Figueira
Departamento de Computacion, FCEyN, UBA
2o cuatrimestre 2015
1
Contenido - Computabilidad
1. Introduccion, maquinas de Turing, funciones parciales, funcionesTuring computables, ejemplos, p.4
2. Funciones iniciales, composicion, recursion, clases PRC, funcionesprimitivas recursivas , p. 23
3. Sumatorias y productorias, cuantificadores acotados, minimizacionacotada, codificacion de pares y secuencias, p. 36
4. LenguajeS, estado, descripcion instantanea, computo, funciones
parciales computables, minimizacion no acotada, p.525. Codificacion de programas, Halting problem, diagonalizacion, tesis
de Church, programa universal,step counter, snapshot, p.73
6. Teorema de la forma normal, teorema del parametro, teorema de larecursion y aplicaciones, teorema del punto fijo, p. 103
7. Conjuntos c.e., teorema de la enumeracion, teorema de Rice yaplicaciones, p.117
8. Opcional - Oraculos, reducibilidad de Turing, jerarqua aritmetica,problemade Post, p.133
2
Contenido - LogicaLogica proposicional
1. Lenguaje de logica proposicional,semantica, tautologa,consecuencia semantica, conjunto satisfacible, sistema axiomaticoSP, consecuencia sintactica, p.146
2. Teorema de la deduccion, lema de Lindenbaum, completitud de SP,compacidad, p.165
Logica de primer orden
1. Lenguaje de logica de primer orden, terminos, formulas, variableslibres y ligadas, interpretacion, valuacion, niveles de verdad,consecuencia semantica, p.182
2. Lema de sustitucion, sistema axiomatico SQ, consecuenciasintactica, teorema de la generalizacion, teorema de lageneralizacion en constantes, p. 202
3. Completitud de SQ,compacidad, p.221
4. Aplicaciones de compacidad, indecidibilidad de la logica de primerorden, p.237
5. Opcional - Teorema de incompletitud de Godel, p.252 3
ComputabilidadClase 1
Introduccion, maquinas de Turing, funciones parciales,funciones Turing computables, ejemplos
4
-
7/25/2019 Lgica y computabilidad
2/66
Organizacion de la materia
Docentes Santiago Figueira (Prof.) Emilia Descotte (JTP) Manuel Gimenez (AY1) Herman Schinca (AY1) Gabriel Senno (AY1) Nahuel Lascano (AY2)
Miercoles de 17 a 19 en aula 4. Viernes de 17 a 22 en aula 9.
www.dc.uba.ar/lyc
5
Aprobacion
Dos parciales, cada uno con su recuperatorio.
La materia puede ser promocionada. Mas detalles, en lapractica.
Examenes: viernes 25/09: primer parcial viernes 13/11: segundo parcial viernes 20/11: primer recuperatorio viernes 27/11: segundo recuperatorio
6
Temas y bibliografa
Computabilidad
Computability, Complexity and Languages, fundamentals oftheoretical computer science. Martin Davis, Ron Sigal, ElaineWeyuker, Elsevier, 1994
Logica proposicional Metalogica, introduccion a la metateora de la l ogica clasica de
primer orden. Geoffrey Hunter, Editorial Paraninfo, 1981.
Logica de primer orden
A mathematical introduction to logic. Herbert Enderton,Elsevier, 2006.
7
Orgenes fines del siglo XIX y principios del siglo XX: interes por los
fundamentos de la matematica dos grandes busquedas (Hilbert)
1. completitud de la aritmetica se buscaba un sistema axiomatico que capturara todas las
verdade s de la arit metica Godel (1931): cualquier sistema axiomatico suficientemente
poderoso es incompleto o inconsistente
2. el problema de la decision (Entscheidungsproblem) se buscaba un procedimiento efectivo para decidir si cualquier
formula de primer orden era valida o no Turing (1936): no existe tal procedimiento efectivo
David Hilbert Kurt Godel Alan Turing 8
-
7/25/2019 Lgica y computabilidad
3/66
Maquinas de Turing
0 1 1 0 0 0 0 1 0 . . .. . .
q
Se compone de : unacinta
dividida en celdas infinita en ambas direcciones cada celda contiene un smbolo de un alfabeto dado .
L,R /
representa el blanco en una celdaL y R son smbol os reser vados (r epresentaran acciones quepuede realizar la cabeza)
unacabeza lee y escribe un smbolo a la vez se mueve una posicion a la izquierda o una posicion a la
derecha unatabla finita de instrucciones
dice que hacer en cada paso9
Tabla de instrucciones es el alfabeto. L, R /, . Qes el conjunto finito de estados A= {L, R} es el conjunto de acciones
un smbolo s se interpreta como escribir s en la posicionactual
Lse interpreta como mover la cabeza una posici on hacia laizquierda
Rse interpreta como mover la cabeza una posicion hacia la
derechaUnatabla de instrucciones Tes un subconjunto (finito) de
Q A Q
La tupla(q, s, a, q) T
se interpreta como
Si la maquina esta en el estadoqleyendo en la cinta elsmbolos, entonces realiza la acciona y pasa al estadoq
10
Ejemplo de ejecucion de una instruccionSupongamos un alfabeto ={0, 1}.Una maquina con esta tabla de instrucciones:
{ (q1, 0, 1, q2) , (q2, 1, R, q1)}
Si empieza en esta configuracion
0 1 1 0 0 0 0 1 0 . . .. . .
q1
pasa a
0 1 1 1 0 0 0 1 0 . . .. . .
q2
y luego a
0 1 1 1 0 0 0 1 0 . . .. . .
q1
11
Definicion de maquina de TuringUnamaquina de Turing es una tupla
(, Q, T, q0, qf)
donde
(finito) es el conjunto smbolos(L, R /, ) Q(finito) es el conjunto deestados
tiene dos estados distinguidos:
q0 Qes el estado inicial qf Qes el estado final
TQ {L, R} Qes latabla de instrucciones va a ser finita porque y Qlo son
cuando no hay restricciones sobre T decimos que M es unamaquina de Turing no determinsitca
cuando no hay dos instrucciones en T que empiezan con lasmismas primeras dos coordenadas, decimos que M es unamaquina de Turing determinstica
12
-
7/25/2019 Lgica y computabilidad
4/66
EjemploSeaM = (, Q, T, q0, qf) con = {, a, b}
Q= {q0, q1, qf}
tabla de instrucciones
T =
q0 a b q1q1 b R q0q0 qf
q1 qf
Visto como automata
q0inicio q1
qf
a/b
b/R/
/
si empieza en a a a a
q0termina en
b b b b qf
si empieza en a a b a
q0termina en
b b b a q0
si empieza en a a b a
q0termina en
a a b a qf
13
Representacion de numeros y tuplasFijamos ={, 1}. representaremos a losnumerosnaturales en unario (con
palotes). el numero x N se representa como
x= 1 . . . 1 x+1
representamos a lastuplas(x1, . . . , xn) como lista de
(representaciones de) los xi separados por blanco la tupla (x1, . . . , xn) se representa como
x1 x2 xn
Por ejemplo,
el numero 0 se representa como 1
el numero 3 se representa como 1111
la tupla (1, 2) se representa como 11 111 la tupla (0, 0, 1) se representa como 1 1 11
14
Funciones parcialesSiempre vamos a trabajar con funciones f : Nn N.
Pero van a ser funciones parciales. Unafuncion parcial f es unafuncion que puede estar indefinida para algunos (tal vez ninguno;tal vez todos) sus argumentos.
notamos f(x1, . . . , xn) cuando f esta definida parax1, . . . , xn. En este caso f(x1, . . . , xn) es un numero natural.
notamos f(x1, . . . , xn) cuando f esta indefinida parax1, . . . , xn
El conjunto de argumentos para los que f esta definida se l lamadominiode f, notado dom(f).
dom(f) = {(x1, . . . , xn) : f(x1, . . . , xn)}
f estotalsi dom(f) = Nn.15
Computo de funciones parciales en maquinas de TuringUna funcion parcial f : Nn Nes Turing computablesi existe unamaquina de Turing determinstica M = (, Q, T, q0, qf) con ={, 1}tal que cuando empieza en la configuracion inicial
. . . x1 x2 . . . xn . . .
q0
(con los enteros xirepresentados en unario y nada mas en la entrada
salvo la representacion de la entrada):
si f(x1, . . . , xn) entonces siguiendo sus instrucciones en T llega auna configuracion final de la forma
. . . f(x1, . . . , xn) . . .
qf
(quiza algo mas en la cinta)
si f(x1, . . . , xn) entonces nunca termina en el estado qf.16
-
7/25/2019 Lgica y computabilidad
5/66
Computo de la funcion f(x) = 0
q0inicio q1 q2 qf/R /1 1/R
17
Computo de la funcion f(x) =x+ 1
q0inicio q1 qf/1 1/R
18
Computo de la funcion f(x) = 2xIdea: por cada 1 que borro de la entrada, pongo 11 bien a la derecha.Repito esto hasta que quede solo un 1 en la entrada. Ah pongo un 1 masa la derecha.
Ejemplo: entrada = 2
1. 1 1 1
2. 1 1 1 1
3. 1 1 1 1 1
4. 1 1 1 1 1 1
Invariante: a lo largo de cada iteraci on, la cinta esta as: 1 . . . 1
n
1 . . . . . . 1 2m
para algunn > 0, m 0, n + m 1 = entrada
1. si n = 1 entonces pongo un 1 mas a la derecha y termina en qf con
1 1 . . . . . . 1 2m+1
2. si n > 1 transformo la cinta en 1 . . . 1 n1
1 . . . . . . 1 2(m+1)
y vuelvo
al paso 1 19
Computo de la funcion f(x) = 2x
q0inicio q1 q2 q11 q12
q13
q14
qf
q3
q4 q5
q6q7q8q9
q10
/L 1/L
1/1
/R
1/
/R
/R/11/R
/1
/ 1/L
1/R 1/R
1/L
/R 1/R
/R
/1
1/R
1/R
20
-
7/25/2019 Lgica y computabilidad
6/66
Computo de una funcion parcial
Supongamos
f(x) =
x si xes par
si no
q0inicio q1 q2 q3 qf
q4
/L 1/L /R
1/R
/
1/L1/L
21
Poder de computo
TeoremaSea f : Nm N una funcion parcial. Son equivalentes:
1. fes computable en Java2. fes computable en C3. f es computable en Haskell
4. f es Turing computable
No es importante que base usamos para representar a los numeros
usamos representacion unaria ( ={, 1}) pero podramos haber elegido la binaria ( = {, 0, 1}) o base 10 ( ={, 0, 1, 2, . . . , 9})
si permitimos que al terminar la cinta tenga otras cosasescritas ademas de la salida o solo contenga la salida
si usamos esta variante de arquitectura: una cinta de entrada (solo de lectura) una cinta de salida (solo de escritura) una o varias cintas de trabajo, de lectura/escritura
Siempre computamos la misma clase de funciones! 22
ComputabilidadClase 2
Funciones iniciales, composicion, recursion, clases PRC,funciones primitivas recursivas
23
Funciones iniciales
Otra manera de formalizar la idea de funcion calculable de maneraefectiva:
empezar por funciones muy simples, efectivas intuitivamente
si mezclamos de alguna manera efectiva dos o mas funcionesque ya eran efectivas, entonces obtenemos una funci oncalculable de manera efectiva
DefinicionLas siguientes funciones se llamaniniciales:
s(x) = x+ 1
n(x) = 0
proyecciones: uni(x1, . . . , xn) = xi para i {1, . . . , n}
24
-
7/25/2019 Lgica y computabilidad
7/66
Composicion y recursion primitiva
DefinicionSeaf : Nk Ny g1, . . . , gk: N
n N. h : Nn Nse obtiene apartir de f y g1, . . . , gk porcomposicionsi
h(x1, . . . , xn) = f(g1(x1, . . . , xn), . . . , gk(x1, . . . , xn))
Definicionh: Nn+1 Nse obtiene a partir de g: Nn+2 Ny f : Nn Nporrecursion primitivasi
h(x1, . . . , xn, 0) = f(x1, . . . , xn)
h(x1, . . . , xn, t + 1) = g(h(x1, . . . , xn, t), x1, . . . , xn, t)
(En este contexto, una funcion 0-aria es una constante k. Sih es1-aria y t= 0, entonces h(t) = k= s(k)(n(t)).)
25
Clases PRC
Una clase C de funciones totales esPRC (primitive recursiveclosed)si
1. las funciones iniciales estan en C
2. si una funcion f se obtiene a partir de otras pertenecientes a
C por medio de composicion o recursion primitiva, entonces ftambien esta en C
TeoremaLa clase de funciones totales Turing computables (o computablesen C, o en Java) es una clase PRC.
26
Funciones primitivas recursivasUna funcion esprimitiva recursiva (p.r.) si se puede obtener apartir de las funciones iniciales por un numero finito deaplicaciones de composicion y recursion primitiva.
TeoremaUna funcion es p.r. sii pertenece a toda clase PRC.
Demostracion.() La clase de funciones p.r. es una clase PRC. Luego, si f
pertenece a toda clase PRC, en particular f es p.r.() Seafp.r. y seaCuna clase PRC. Como fes p.r., hay una lista
f1, f2, . . . , fntal que
f =fn fies inicial (luego esta en C) o se obtiene por composicion o
recursion primitiva a partir de funciones fj, j< i (luegotambien esta enC).
Entonces todas las funciones de la lista estan en C(porinduccion). En particular, fn C. 27
Funciones totales Turing computables = funcionesprimitivas recursivas?
Entonces la clase de funciones p.r. es la clase PRC mas chica.
CorolarioToda funcion p.r. es total y Turing computable.
Demostracion.Sabemos que la clase de funciones totales Turing computables esPRC. Por el teorema anterior, si fes p.r., entonces f pertenece ala clase de funciones Turing computables.
No toda funcionparcialTuring computable es p.r porque todafuncion p.r. es total. Pero...
toda funcion total Turing computable es p.r.?
28
-
7/25/2019 Lgica y computabilidad
8/66
Ejemplo de funcion p.r.
La funcionsuma(x, y) = x+ y
es p.r., porque
suma(x, 0) = u11(x)
suma(x, y + 1) = g(suma(x, y), x, y)
dondeg(x1, x2, x3) = s(u
31(x1, x2, x3))
29
Otras funciones primitivas recursivas
x y
x!
xy
xy= x y si x y0 si no (x) =
1 si x= 0
0 si no
y muchas mas. Todas las funciones totales Turingcomputables..?
30
Predicados primitivos recursivos
Lospredicadosson simplemente funciones que toman valores en{0, 1}.
1 se interpreta como verdadero
0 se interpreta como falso
Lospredicados p.r.son aquellos representados por funciones p.r. en{0, 1}.
Por ejemplo, el predicado x yes p.r. porque se puede definircomo
(xy)
31
Operadores logicos
TeoremaSeaCuna clase PRC. Sipyq son predicados en Centoncesp,p qyp qestan en C.
Demostracion.
pse define como (p)
p qse define como p q
p qse define como (p q)
CorolarioSipyqson predicados p.r., entonces tambien lo son lospredicadosp, p qyp q
CorolarioSipyqson predicados totales Turing computables entoncestambien lo son los predicadosp, p qyp q
32
-
7/25/2019 Lgica y computabilidad
9/66
Definicion por casos (2)
TeoremaSeaCuna clase PRC. Sean h , g: Nn N funciones en Cy seap: Nn {0, 1} un predicado en C. La funcion
f(x1, . . . , xn) = g(x1, . . . , xn) sip(x1, . . . , xn)h(x1, . . . , xn) si noesta en C.
Demostracion.f(x1, . . . , xn) =g(x1, . . . , xn) p(x1, . . . , xn) +h(x1, . . . , xn) (p(x1, . . . , xn))
33
Definicion por casos (m + 1)
TeoremaSeaCuna clase PRC. Sean g1, . . . , gm, h: Nn N funciones en Cy sean p1, . . . , pm: N
n {0, 1}predicados mutuamenteexcluyentes en C. La funcion
f(x1, . . . , xn) =
g1(x1, . . . , xn) sip1(x1, . . . , xn)...
gm(x1, . . . , xn) sipm(x1, . . . , xn)
h(x1, . . . , xn) si no
esta en C.
34
Recursion primitiva
todava no respondimos si p.r. = Turing computables totales
no lo vamos a responder todava
Observar que el esquema de recursion
h(x1, . . . , xn, 0) = f(x1, . . . , xn)
h(x1, . . . , xn, t+ 1) = g(h(x1, . . . , xn, t), x1, . . . , xn, t)
es muy simple:
la recursion siempre se hace en el ultimo parametro
la funcion variante de h(x1, . . . , xn, xn+1) es xn+1
35
ComputabilidadClase 3
Sumatorias y productorias, cuantificadores acotados,minimizacion acotada, codificacion de pares y secuencias
36
-
7/25/2019 Lgica y computabilidad
10/66
Sumatorias y productorias (desde 0)
TeoremaSeaCuna clase PRC. Sif : Nn+1 Nes ta en Centonces tambienestan las funciones
g(y, x1, . . . , xn) =
yt=0
f(t, x1, . . . , xn)
h(y, x1, . . . , xn) =
yt=0
f(t, x1, . . . , xn)
Demostracion.g(0, x1, . . . , xn) = f(0, x1, . . . , xn)
g(t+ 1, x1, . . . , xn) = g(t, x1, . . . , xn) +f(t+ 1, x1, . . . , xn)
Idem para h con en lugar de +.
Observar que no importa la variable en la que se hace la recursion:
podemos definir g(x, t) como la clase pasada y luego
g(t, x) = g(u22 (t, x), u21 (t, x)) = g
(x, t). 37
Sumatorias y productorias (desde 1)
TeoremaSeaCuna clase PRC. Sif : Nn+1 Nes ta en Centonces tambienestan las funciones
g(y, x1, . . . , xn) =
yt=1
f(t, x1, . . . , xn)
h(y, x1, . . . , xn) =
yt=1
f(t, x1, . . . , xn)
(como siempre, sumatoria vaca = 0, pro ductoria vaca = 1)
Demostracion.g(0, x1, . . . , xn) = 0
g(t+ 1, x1, . . . , xn) = g(t, x1, . . . , xn) +f(t+ 1, x1, . . . , xn)
Idem para h con en lugar de + y 1 en lugar de 0 en el casobase.
38
Cuantificadores acotadosSeap: Nn+1 {0, 1}un predicado.
(t)y p(t, x1, . . . , xn)es verdadero sii
p(0, x1, . . . , xn) es verdaderoy...
p(y, x1, . . . , xn) es verdadero
(t)y p(t, x1, . . . , xn)es verdadero sii p(0, x1, . . . , xn) es verdaderoo
...
p(y, x1, . . . , xn) es verdadero
Lo mismo se puede definir con < yen lugar de y.
(t)
-
7/25/2019 Lgica y computabilidad
11/66
Cuantificadores acotados (con
-
7/25/2019 Lgica y computabilidad
12/66
Mas ejemplos de funciones primitivas recursivas
x div yes la division entera de x pory
mntx
((t+ 1) y> x)
Notar que con esta definicion 0 div 0 es 0.
x mod yes el resto de dividir a x por y
pn es el n-esimo primo (n> 0). Se define
p0= 0, p1= 2, p2= 3, p3= 5, . . .
p0 = 0
pn+1 = mntK(n)
(primo(t) t> pn)
Necesitamos una cota K(n)que sea buena, i.e. suficientemente grande y primitiva recursiva
K(n) = pn! + 1 funciona (ver que pn+1 pn! + 1).
45
Codificacion de pares
Definimos la funcion primitiva recursiva
x, y= 2x(2 y+ 1)1
Notar que 2x(2 y+ 1) = 0.
Proposicion
Hay una unica solucion (x, y) a la ecuacionx, y= z.
Demostracion.
xes el maximo numero tal que 2x|(z+ 1)
y= ((z+ 1)/2x 1) div 2
46
Observadores de paresLosobservadoresdel par z= x, y son
l(z) = x
r(z) = y
Proposicion
Los observadores de pares son primitivas recursivas.
Demostracion.
Comox, y< z+ 1 tenemos que l(z) = mnxz((y)z z= x, y)
r(z) = mnyz((x)z z= x, y)
Por ejemplo,
2, 5= 22(2 5 + 1)1 = 43
l(43) = 2
r(43) = 547
Codificacion de secuencias
Elnumero de Godelde la secuencia
a1, . . . , an
es el numero
[a1, . . . , an] =n
i=1paii ,
donde pies el i-esimo primo (i 1).
Por ejemplo el numero de Godel de la secuencia
1, 3, 3, 2, 2
es[1, 3, 3, 2, 2] = 21 33 53 72 112 = 40020750.
48
-
7/25/2019 Lgica y computabilidad
13/66
Propiedades de la codificacion de secuencias
TeoremaSi[a1, . . . , an] = [b1, . . . , bn]entoncesa i= bi para todoi {1, . . . , n}.
Demostracion.Por la factorizacion unica en primos.
Observar que
[a1, . . . , an] = [a1, . . . , an, 0] = [a1, . . . , an, 0, 0] = . . .
pero[a1, . . . , an]= [0, a1, . . . , an]
49
Observadores de secuenciasLosobservadoresde la secuencia x= [a1, . . . , an] son x[i] = ai |x|= longitud de x
Proposicion
Los observadores de secuencias son primitivas recursivas.
Demostracion.
x[i] = mntx(pt+1
i |x) |x|= mnix(x[i]= 0 (j)x(j i x[j] = 0))
Por ejemplo, [1, 3, 3, 2, 2][2] = 3 = 40020750[2] [1, 3, 3, 2, 2][6] = 0 = 40020750[6] |[1, 3, 3, 2, 2]|= 5 =|40020750| |[1, 3, 3, 2, 2, 0]|=|[1, 3, 3, 2, 2, 0, 0]|= 5 =|40020750| x[0] = 0 para todo x 0[i] = 0 para todo i 50
En resumen: codificacion y decodificacion de pares ysecuencias
Teorema (Codificacion de pares)
l(x, y) = x, r(x, y) = y
z= l(z), r(z)
l(z), r(z) z
la codificacion y observadores de pares son p.r.
Teorema (Codificacion de secuencias)
[a1, . . . , an][i] =
ai si1 i n
0 si no
sin |x| entonces[x[1], . . . , x[n]] = x
la codificacion y observadores de secuencias son p.r.
51
ComputabilidadClase 4
LenguajeS, estado, descripcion instantanea, computo,funciones parciales computables, minimizacion no acotada
52
-
7/25/2019 Lgica y computabilidad
14/66
Lenguaje de programacionS(Davis/Sigal/Weyuker) resulta igual de poderoso que las maquinas de Turing, pero es
mas faci l de programar imperativo, muy simple
variables de entrada: X1, X2, . . .
unica variable de salida: Yvariables temporales: Z1, Z2, . . .
empiezan inicializadas en 0
las variables almacenan numeros naturales 3 instrucciones (cada una puede o no estar etiquetada):
1. V V+ 1 la variable Vse incrementa en 1
2. V V 1 Vse decrementa en 1 si antes era > 0; si no queda en 0 es el V1 que ya vimos
3. IFV = 0 GOTOA condicional muy primitivo A es una etiqueta que denota una instruccion del programa si el valor de Ves distinto de 0, la ejecucion sigue con la
primera instruccion que tenga etiqueta A si el valor de Ves 0, sigue con la pr oxima instruccion
programa = sucesion finita de instrucciones 53
Ejemplo 1
ProgramaP
[A] XX 1Y Y+ 1IF X= 0 GOTO A
Ejecucion paraentradaX= 3:
X Y
3 02 11 20 3
escribimos X por X1; Z por Z1 P termina cuando X= 0 porque no hay siguiente instruccion
Pcomputa la funcion f : N N,
f(x) =
x si x= 0
1 si no
siempre deja la variable X en 0
54
Ejemplo 2
[A] IF X= 0 GOTO B
ZZ+ 1
IF Z= 0 GOTO E
[B] XX 1
Y Y+ 1
ZZ+ 1
IF Z= 0 GOTO A
computa la funcion f : N N, f(x) = x cuando intenta ir a E, termina en el ejemplo, Z solo sirve para un salto incondicional. En
general GOTO L es equivalente a
V V+ 1
IF V= 0 GOTO L
dondeVes una variable nueva (en el ejemplo es Z) 55
Macros
S no tiene salto incondicional pero podemos simularlo con GOTO L lo usamos, como si fuera parte del lenguaje, pero:
cada vez que apareceGOTOL
en un programa P, lo reemplazamos con
V V+ 1
IFV = 0 GOTOL
donde Vtiene que ser una variable que no aparece en P.
Vamos a ver que se pueden simular muchas otras operaciones.Una vez que sepamos que se pueden escribir en el lenguaje S, lasusamos como si fueran propias (sonpseudoinstrucciones).
la forma abreviada se llama macro
el segmento de programa que la macro abrevia se llamaexpansion del macro
56
-
7/25/2019 Lgica y computabilidad
15/66
Asignacion de cero: V 0
En un programa P, la pseudoinstruccion V 0 se expande como
[L] V V 1
IF V = 0 GOTO L
donde L es una etiqueta que no aparece en P
57
Asignacion de variables: Y X
Y 0
[A] IF X= 0 GOTO B
GOTO C
[B] XX 1
Y Y + 1
Z Z+ 1GOTO A
[C] IF Z= 0 GOTO D
GOTO E
[D] Z Z 1
XX+ 1
GOTO C
el primer ciclo copia el valor deX en Y y en Z; deja Xen cero
el segundo ciclo pone en X elvalor que tena originalmente ydejaZen cero
se usa la macro GOTO A
no debe expandirse como
Z Z+ 1
IF Z= 0 GOTOA
sino como
Z2 Z2+ 1
IF Z2= 0 GOTOA
58
Asignacion de variables: V V
Y 0
[A] IF X= 0 GOTO B
GOTO C
[B] XX 1
Y Y + 1
ZZ+ 1
GOTO A
[C] IF Z= 0 GOTO D
GOTO E
[D] ZZ 1
XX+ 1
GOTO C
se puede usar para asignar a lavariableVel contenido de la variableV y dejar V sin cambios dentro deun programa Pcualquiera: V V.
cambiar Y por V cambiar X por V
cambiar Z por una variabletemporal que no aparezca en P
cambiar A, B, C, D poretiquetas que no aparezcan en P
59
Suma de dos variables
Y X1
Z X2
[B] IF Z= 0 GOTO A
GOTO E
[A] Z Z 1
Y Y+ 1
GOTO B
computa la funcion f : N N N
f(x1, x2) = x1+x2
60
-
7/25/2019 Lgica y computabilidad
16/66
Resta de dos variables
Y X1
ZX2
[C] IF Z= 0 GOTO A
GOTO E
[A] IF Y = 0 GOTO B
GOTO A
[B] Y Y 1
ZZ 1
GOTO C
computa la funcion g: N N N
g(x1, x2) =
x1 x2 si x1 x2
si no
ges una funcionparcial
la indefinicion se nota con
(en el metalenguaje) el comportamiento del
programa que se indefinees lano terminacion
no hay otra causa deindefinicion
61
EstadosUnestadode un programa Pes una lista de ecuaciones de laforma V =m (donde Ves una variable y m es un numero) tal que
hay una ecuacion para cada variable que se usa en P
no hay dos ecuaciones para la misma variable
Por ejemplo, para P:
[A] XX 1
Y Y+ 1
IF X= 0 GOTO A
son estados de P:
X = 3, Y = 1 X = 3, Y = 1, Z= 0 X = 3, Y = 1, Z= 8
no hace falta quesea alcanzado
no son estados de P:
X = 3 X = 3, Z= 0 X = 3, Y = 1, X= 0
62
Descripcion instantaneaSupongamos que el programa P tiene longitud n .Para un estado de P y un i {1, . . . , n+ 1},
el par (i, ) es unadescripcion instantaneade P (i, ) se llamaterminalsi i= n+ 1
Para un (i, ) no terminal, podemos definir su sucesor(j, ) como:
1. si la i-esima instruccion de P es V V+ 1. j= i+ 1
es , salvo que V =m se reemplaza por V =m+ 12. si la i-esima instruccion de P es V V 1. j= i+ 1 es , salvo que V =m se reemplaza por V= max{m 1, 0}
3. si la i-esima instruccion de Pes IF V = 0 GOTO L es identico a
3.1 si tiene V= 0 entonces j= i+ 13.2 si tiene V =m para m = 0 entonces
si existe en P una instruccion con etiqueta L entoncesj= mn {k: k-esima instrucc ion de P tiene etiqueta L}
si no j= n + 1
63
Computos
Uncomputode un programa Pa partir de una descripcioninstantanea d1 es una lista
d1, d2, . . . , dk
de descripciones instantaneas de Ptal que
di+1 es sucesor de di para i {1, 2, . . . , k 1}
dkes terminal
64
-
7/25/2019 Lgica y computabilidad
17/66
Estados y descripciones iniciales
SeaPun programa y sean r1, . . . , rm numeros dados.
elestado inicialde P para r1, . . . , rm es el estado 1, que tiene
X1= r1 , X2= r2 , . . . , Xm= rm , Y = 0
junto con
V = 0para cada variable V que aparezca en Py no seaX1, . . . , Xm, Y
ladescripcion inicialde P para r1, . . . , rm es
(1, 1)
65
Computos a partir del estado inicialSeaPun programa y sean r1, . . . , rm numeros dados 1 el estado inicial
Dos casos hay un computo de P
d1, . . . , dk
tal que d1= (1, 1)
Notamos(m)P (r1, . . . , rm)al valor de Y en dk.
en particular, (m)P (r1, . . . , rm) esta definido (not.
(m)P (r1, . . . , rm))
no hay tal computo, i.e. existe una secuencia infinita
d1, d2, d3, . . .
donde d1= (1, 1). di+1 es sucesor de di
Decimos que(m)P (r1, . . . , rm)esta indefinido (not.
(m)P (r1, . . . , rm))
66
Funciones computablesUna funcion (parcial) f : Nm Nes S-parcial computable (osimplementeparcial computable) si existe un programa Ptal que
f(r1, . . . , rm)=(m)P (r1, . . . , rm)
para todo (r1, . . . , rm) Nm.
La igualdad (del meta-lenguaje) es verdadera si
los dos lados estan definidos y tienen el mismo valor o
los dos lados estan indefinidosLa funcion f esS-computable(o simplementecomputable) si esparcial computable y total.
Notar que un mismo programa Ppuede servir para computarfunciones de 1 variable, 2 variables, etc. Supongamos que en PapareceXn y no aparece Xi para i> n
si solo se especifican m < n variables de entrada,Xm+1, . . . , Xn toman el valor 0
si se especifican m > n variables de entrada, Pignorara Xn+1, . . . , Xm 67
Minimizacion no acotada
Recordar la definicion deminimizacion acotada:
mnty
p(t, x1, . . . , xn) =
mnimo t ytal que
p(t, x1, . . . , xn) es verdaderosi existe tal t
0 si no
Definimos laminimizacion no acotada
mnt
p(t, x1, . . . , xn) =
mnimo ttal que
p(t, x1, . . . , xn) es verdaderosi existe tal t
si no
68
-
7/25/2019 Lgica y computabilidad
18/66
Minimizacion no acotada
TeoremaSip: Nn+1 {0, 1} es un predicado computable entonces
mnt
p(t, x1, . . . , xn)
es parcial computable.
Demostracion.El siguiente programa computa mntp(t, x1, . . . , xn):
[A] IF p(Y, X1, . . . , Xn) = 1 GOTO E
Y Y + 1
GOTO A
69
Clausura por composicion
TeoremaSih se obtiene a partir de las funciones (parciales) computables
f, g1, . . . , gk por composicion entoncesh es (parcial) computable.
Demostracion.El siguiente programa computa h :
Z1 g1(X1, . . . , Xn)...
Zk gk(X1, . . . , Xn)
Y f(Z1, . . . , Zk)
Sif, g1, . . . , gk son totales entonces h es total.
70
Clausura por recursion primitiva
TeoremaSih se obtiene a partir deg por recursion primitiva yg escomputable entoncesh es computable.
Demostracion.El siguiente programa computa h :
Y k (es una macro, se puede hacer facil)[A] IF X= 0 GOTO E (otra macro, condicion del IF por =)
Y g(Z, Y)
ZZ+ 1
XX 1
GOTO ASig es total entonces h es total.
71
Las funciones computables forman una clase PRC
TeoremaLa clase de funciones computables es una clase PRC.
Demostracion.Ya vimos que la clase de funciones computables esta cerrada porcomposicion (p.70) y recursion primitiva (p.71). Veamos que lasfunciones iniciales son computables:
s(x) = x+ 1 se computa con el programaY X+ 1
n(x) = 0 se computa con el programa vaco
uni(x1, . . . , xn) = xi se computa con el programa
Y Xi
CorolarioToda funcion primitiva recursiva es computable.
72
-
7/25/2019 Lgica y computabilidad
19/66
ComputabilidadClase 5
Codificacion de programas, Halting problem, diagonalizacion,tesis de Church, programa universal, step counter, snapshot
73
Tipos de datos en S
vimos que el unico tipo de dato en S son los naturales sin embargo podemos simular otros tipos. Por ejemplo,
tipo bool: lo representamos con el 1 (verdadero) y el 0 (falso) tipo par de numeros naturales: la codificacion y decodificacion
de pares son funciones primitivas recursivas
tipo entero: po dra ser codificada con un parbool, numero natural
tipo secuencias finitas de numeros naturales: la codificacion ydecodificacion de secuencias son funciones primitivas recursivas
ahora vamos a ver como simular eltipo programa en S
74
Codificacion de programas en S
Recordemos que las instrucciones de Seran:
1. V V+ 1
2. V V 1
3. IF V = 0 GOTO L
Por conveniencia vamos a agregar una cuarta instruccion
4. V V: no hace nada
Observar que toda instruccion
puede o no estar etiquetada con L
menciona exactamente una variable V
el IF ademas menciona siempre una etiqueta L
75
Codificacion de variables y etiquetas deS
Ordenamos las variables:
Y, X1, Z1, X2, Z2, X3, Z3, . . .
Ordenamos las etiquetas:
A, B, C, D, . . . , Z, AA, AB, AC, . . . , AZ, BA, BB, . . . , BZ, . . .
Escribimos #(V) para la posicion que ocupa la variable Ven lalista. Idem para #(L) con la etiqueta L
Por ejemplo,
#(Y) = 1
#(X2) = 4
#(A) = 1
#(C) = 3
76
-
7/25/2019 Lgica y computabilidad
20/66
Codificacion de instrucciones de SCodificamos a la instruccion I con
#(I) = a, b, c
donde
1. si I tiene etiqueta L, entonces a = #(L); si no a = 02. si la variable mencionada en I es V entonces c= #(V) 13. si la instruccion I es
3.1 V V entonces b= 0
3.2 V V+ 1 entonces b= 13.3 V V 1 entonces b= 23.4 IFV = 0 GOTOL entonces b= #(L) + 2
Por ejemplo, #(XX+ 1) =0, 1, 1=0, 5= 10 #([A] XX+ 1) =1, 1, 1=1, 5= 21 #(IF X= 0 GOTO A) = 0, 3, 1=0, 23= 46 #(Y Y) = 0, 0, 0=0, 0= 0
Todo numeroxrepresenta a una unica instruccion I.77
Codificacion de programas en S
Un programa P es una lista (finita) de instrucciones I1, . . . , Ik
Codificamos al programa P con
#(P) = [#(I1), . . . , #(Ik)] 1
Por ejemplo, para el programa P
[A] XX+ 1
IF X= 0 GOTO A
tenemos
#(P) = [#(I1), #(I2)] 1 = [21, 46] 1 = 221 346 1
78
AmbiguedadesDijimos que P
[A] XX+ 1
IF X= 0 GOTO A
tiene numero [21, 46] 1. Pero
[21, 46] = [21, 46, 0]
Un mismo numero podra representar a mas de un programa!
Por suerte, el programa [21, 46, 0] es
[A] XX+ 1
IF X= 0 GOTO A
Y Y
y es equivalente a P.
De todos modos, eliminamos esta ambiguedad estipulando que
la instruccion final de un programa no puede ser Y Y
Con esto, cada numero representa a ununicoprograma. 79
Hay mas funciones N Nque numeros naturales
Teorema (Cantor)
El conjunto de las funciones (totales) N N no es numerable.
Demostracion.Supongamos que lo fuera. Las enumero: f0, f1, f2. . .
valores de f0 = f0(0) f0(1) f0(2) f0(3) . . .valores de f1 = f1(0) f1(1) f1(2) f1(3) . . .valores de f
2 = f
2(0) f
2(1) f
2(2) f
2(3) . . .
...valores de fk = fk(0) fk(1) fk(2) fk(3) . . .
... . . .
Defino la siguiente funcion g: N N
g(x) = fx(x) + 1.
Para todo k, fk=g (en particular difieren en el punto k).Entoncesgno esta listada. Absurdo: f0, f1, f2. . . era unaenumeracion detodaslas funciones N N. 80
-
7/25/2019 Lgica y computabilidad
21/66
Hay funciones no computables
hay una cantidad no numerable de funciones N N
o sea, hay mas funciones N Nque numeros naturales
hay tantos programas como numeros naturales
hay tantas funciones computables como numeros naturales tiene que haber funciones N Nno computables
Pero que ejemplo concreto tenemos?
81
El problema de la detencion (halting problem)HALT(x, y) : N2 {0, 1}es verdadero sii el programa con numeroy y entrada xno se indefine, i.e.
HALT(x, y) =
1 si
(1)P (x)
0 si no
donde Pes el unico programa tal que #(P) = y.
Ejemplo:
(pseudo)programaP
Y 2[A] Y Y+ 2
IF (a)Y(b)Y [Primo(a)Primo(b)a+b= Y] GOTOA
Supongamos que #(P) = e. Cuanto vale HALT(x, e)?
HALT(x, e) = 1 sii P(x) sii la conjetura de Goldbach es falsa
82
HALT no es computableTeorema (Turing, 1936)
HALTno es computable.
Demostracion.Supongamos que HALT es computable.Construimos el siguiente programa:
ProgramaQ
[ A] IF HALT(X, X) = 1 GOTO A
Supongamos que #(Q) = e. Entonces
Q(x) =
si HALT(x, x) = 1
0 si no
Entonces
HALT(x, e) = 1 sii Q(x) sii HALT(x, x)= 1
eesta fijo pero xes variable. Llegamos a un absurdo con x= e. 83
DiagonalizacionEn general, sirve para definir una funcion distinta a muchas otras.
En el caso de HALT(x, y),
sea Piel programa con numeroi supongo que HALT(x, y) es computable defino una funcion f computable nucleo de la demostracion: ver que f / {P0 , P1 , P2 , . . . }
para esto, me aseguro que f(x)= Px(x), en particular:
f(x) sii Px(x)P2 (0) P2 (1) P2 (2) . . .
P1 (0) P1 (1) P1 (2) . . .
P0 (0) P0 (1) P0 (2) . . .
pero f era computable! Absurdo: tena que estar en
{P0 , P1 , P2 , . . . }.
84
-
7/25/2019 Lgica y computabilidad
22/66
Tesis de Church
Hay muchos modelos de computo.Esta probado que tienen el mismo poder queS
C
Java
Haskell
maquinas de Turing
...
Tesis de Church.Todos losalgoritmospara computar en losnaturales se pueden programar en S.
Entonces, el problema de la detencion dice
no hay algoritmo para decidir la verdad o falsedad de
HALT(x, y)
85
Universalidad
Para cada n > 0 definimos
(n)(x1, . . . , xn, e) = salida del programae con entrada x1, . . . , xn
= (n)P (x1, . . . , xn) donde #(P) = e
Teorema
Para cada n > 0 la funcion (n)
es parcial computable.
Observar que el programa para (n) es uninterprete de programas.Se trata de un programa que interpreta programas (representadospor numeros).
Para demostrar el teorema, construimos el programa Un quecomputa (n).
86
Idea de UnUn es un programa que computa
(n)(x1, . . . , xn, e) = salida del programae con entrada x1, . . . , xn
= (n)P (x1, . . . , xn) donde #(P) = e
Un necesita
averiguar quien es P (decodifica e)
llevar cuenta de losestadosde Pen cada paso parte del estado inicial de Pcuando la entrada es x1, . . . , xn codifica los estados con listas por ejemplo Y = 0, X1= 2, X2= 1 lo codifica como
[0, 2, 0, 1] = 63
En el codigo de Un Kindica el numero de instruccion que se esta por ejecutar (en
la simulacion de P)
Sdescribe el estado de Pen cada momento
87
Inicializacion
// entrada = x1, . . . , xn, e
// #(P) = e= [i1, . . . , im] 1
Z Xn+1+ 1
// Z= [i1, . . . , im]
Sn
j=1
(p2j)Xj
// S= [0, X1, 0, X2, . . . , 0, Xn] es el estado inicial
K 1
// la primera instruccion de Pa analizar es la 1
88
-
7/25/2019 Lgica y computabilidad
23/66
Ciclo principal
// Scodifica el estado, Kes el numero de instruccion
// Z= [i1, . . . , im]
[C] IF K= |Z| + 1 K= 0 GOTO F
// si llego al final, terminar (ya veremos K = 0)
// si no, sea
Z[K
] =iK =
a,
b, c
U r(Z[K])
// U= b, c
P pr(U)+1// la variable que aparece eniKes la c+ 1-esima
// Pes el primo para la variable que aparece en iK
89
Ciclo principal (cont.)
// Scodifica el estado, Kes el numero de instruccion
// Z= [i1, . . . , im], iK= a, b, c, U= b, c
// Pes el primo para la variable V que aparece en iK
IF l(U) = 0 GOTO N
// si se trata de una instruccion V V salta a N
IF l(U) = 1 GOTO S
// si se trata de una instruccion V V+ 1 salta a S
// si no, es de la forma V V 1 o IF V= 0 GOTO L
IF(P|S) GOTO N
// si Pno divide a S (i.e. V= 0), salta a N
IF l(U) = 2 GOTO R
// V = 0. Si se trata de una instruccion V V 1, salta a R
90
Caso IF V = 0 GOTO L y V = 0
// Scodifica el estado, Kes el numero de instruccion
// Z= [i1, . . . , im], iK= a, b, c, U= b, c
// Pes el primo para la variable V que aparece en iK
// V = 0 y se trata de la instrucci on IF V = 0 GOTOL
// b 2, por lo tanto L es la (b 2)-esima etiquetaK mn
j|Z|(l(Z[j]) + 2 =l(U))
// K pasa a ser la primera instruccion con etiquetaL
// si no hay tal instruccion, K= 0 (saldra del ciclo)
GOTO C
// vuelve a la primera instruccion del ciclo principal
91
CasoR(Resta)
// Scodifica el estado, Kes el numero de instruccion
// Z= [i1, . . . , im], iK =a, b, c, U= b, c
// Pes el primo para la variable V que aparece en iK
// se trata deVV 1 con V = 0
[R] S S div P
GOTO N
// S=nuevo estado de P(resta 1 a V) y salta a N
92
-
7/25/2019 Lgica y computabilidad
24/66
CasoS(Suma)
// S codifica el estado, Kes el numero de instruccion
// Z= [i1, . . . , im], iK= a, b, c, U= b, c
// Pes el primo para la variable V que aparece en iK
// se trata deV V+ 1[S] S S P
GOTO N
// S= nuevo estado de P(suma 1 a V) y salta a N
93
CasoN(Nada)
// Scodifica el estado, Kes el numero de instruccion
// Z= [i1, . . . , im], iK= a, b, c, U= b, c
// Pes el primo para la variable V que aparece en iK
// la instruccion no cambia el estado
[N] KK+ 1
GOTO C
// S no cambia
// K pasa a la siguiente instruccion
// vuelve al ciclo principal
94
Devolucion del resultado
// Scodifica el estado final de P
// sale del ciclo principal
[F] Y S[1]// Y= el valor que toma la variable Y de Pal terminar
95
Todo junto
Z Xn+1+ 1
Sn
i=1
(p2i)Xi
K 1
[C] IF K= |Z| + 1 K= 0 GOTOF
U r(Z[K])
P pr(U)+1IF l(U) = 0 GOTON
IF l(U) = 1 GOTOS
IF(P|S) GOTON
IF l(U) = 2 GOTOR
K mni|Z|
(l(Z[i]) + 2 =l(U))
GOTOC
[R] S S divP
GOTON
[S] S S P
GOTON
[N] K K+ 1
GOTOC
[F] Y S[1]
96
-
7/25/2019 Lgica y computabilidad
25/66
Notacion
A veces escribimos
(n)e (x1, . . . , xn) =
(n)(x1, . . . , xn, e)
A veces omitimos el superndice cuando n = 1
e(x) = (x, e) = (1)(x, e)
97
Step Counter
Definimos
STP(n)(x1, . . . , xn, e, t) sii el programa e termina en
to menos pasos con entrada x1, . . . , xn
sii hay un computo del programa e
de longitud t+ 1, comenzandocon la entrada x1, . . . , xn
TeoremaPara cada n > 0, el predicadoSTP(n)(x1, . . . , xn, e, t)es p.r.
98
Snapshot
Definimos
SNAP(n)(x1, . . . , xn, e, t) = representacion de la configuracion
instantanea del programa e
con entrada x1, . . . , xn en el paso t
La configuracion instantanea se representa como
numero de instruccion, lista representando el estado
TeoremaPara cada n > 0, el predicadoSNAP(n)(x1, . . . , xn, e, t)es p.r.
99
Una funcion computable que no es primitiva recursiva se pueden codificar los programas de Scon constructores y
observadores p.r. se pueden codificar las definiciones de funciones p.r. con
constructores y observadores p.r. existe
(n)e (x1, . . . , xn) parcial computable que simula al e-esimo
programa con entrada x1, . . . , xn existe
(n)e (x1, . . . , xn) computable que simula a la e-esima funcion
p.r. con entrada x1, . . . , xn.Analicemosg: N Ndefinida como g(x) = (1)x (x)
claramente g es computable supongamos que ges p.r.
entonces tambien es p.r. la funci onf(x) = g(x) + 1 =(1)x (x) + 1
existe un e tal quee= f tendr amos e(x) = f(x) = x(x) + 1 eesta fijo pero xes variable instanciando x= e, e(e) = f(e) = e(e) + 1. Absurdo.
por que esto no funciona para parcial comp. en lugar de p.r.?100
-
7/25/2019 Lgica y computabilidad
26/66
La funcion de Ackermann (1928)
A(x, y, z) =
y+ z si x= 0
0 si x= 1 y z= 0
1 si x= 2 y z= 0
y si x> 2 y z= 0
A(x 1, y, A(x, y, z 1)) s ix, z> 0
A0(y, z) = A(0, y, z) = y+ z= y+1 + + 1 zveces
A1(y, z) = A(1, y, z) = y z= y+ +y zveces
A2(y, z) = A(2, y, z) = y z= yz =y y zveces
A3(y, z) = A(3, y, z) = y z= yy.
.
.
y
zveces
. . .
Para cada i, A i: N2 Nes p.r. pero A : N3 Nno es p.r. 101
Version de Robinson & Peter (1948)
B(m, n) =
n+ 1 si m = 0
B(m 1, 1) si m > 0 y n = 0
B(m 1, B(m, n 1)) si m > 0 y n > 0
B0(n) = B(0, n) = n + 1 B1(n) = B(1, n) = 2 + (n+ 3) 3 B2(n) = B(2, n) = 2 (n+ 3) 3 B3(n) = B(3, n) = 2 (n+ 3) 3 B4(n) = B(4, n) = 2 (n+ 3) 3 . . .
Para cada i, Bi: N Nes p.r. pero B: N2 Nno es p.r.
B(4, 2)2 1019728
B(x) = B(x, x) crece mas rapido que cualquier funcion p.r.
(f p.r.)(n)(x> n) B(x)> f(x)
102
ComputabilidadClase 6
Teorema de la forma normal, teorema del parametro, teoremade la recursion y aplicaciones, teorema del punto fijo
103
Teorema de la Forma Normal
TeoremaSea f : Nn N una funcion parcial computable. Entonces existeun predicado p.r. R: Nn+1 Ntal que
f(x1, . . . , xn) = l
mnz
R(x1, . . . , xn, z)
Demostracion.
Seaeel numero de algun programa para f(x1, . . . , xn).Recordar que la configuracion instantanea se representa como
numero de instruccion, lista representando el estado
El siguiente predicado R(x1, . . . , xn, z) es el buscado:
STP(n)(x1, . . . , xn, e, r(z))
l(z) = r
SNAP(n)(x1, . . . , xn, e, r(z))
estado final de econ entrada x1, . . . , xn
[1]
valor de la variable Yen ese estado final 104
-
7/25/2019 Lgica y computabilidad
27/66
Otra caracterizacion de funciones computables
TeoremaUna funcion esparcial computable si se puede obtener a partir delas funciones iniciales por un numero finito de aplicaciones de
composicion,
recursion primitiva y
minimizacion
TeoremaUna funcion escomputablesi se puede obtener a partir de lasfunciones iniciales por un numero finito de aplicaciones de
composicion,
recursion primitiva y
minimizacion propia
(del tipomntq(x1, . . . , xn, t) donde siempre existe al menos unt
tal queq(x1, . . . , xn, t) es verdadero)
105
Eliminando variables de entrada
Consideremos un programa Pque usa la entrada X1 y X2:
INSTRUCCION 1 #(I1)...
INSTRUCCION k #(Ik)
Computa la funcion f : N2 N
f(x, y) = (2)P (x, y)
#(P) = [#(I1), . . . , #(Ik)] 1
Busco numero de programa P0 para f0: N N, f0(x) = f(x, 0)
[A]X2 X2 1 109IF X2= 0 GOTOA 110
INSTRUCCION 1 #(I1)...
INSTRUCCION k #(Ik)
Computa la funcion f0: N N
f0(x) = (1)P0
(x)
#(P0) = [109, 110, #(I1), . . . , #(Ik)]1
106
Eliminando variables de entradaBusco numero de programa P1 para f1: N N, f1(x) = f(x, 1)
[A]X2 X2 1 109IF X2= 0 GOTOA 110
X2 X2+ 1 26
INSTRUCCION 1 #(I1)...
INSTRUCCION k #(Ik)
Computa la funcion f1: N N
f1(x) = (1)P1
(x)
#(P1) =[109, 110, 26, #(I1), . . . , #(Ik)] 1
Busco numero de programa P2 para f2: N N, f2(x) = f(x, 2)
[A]X2 X2 1 109IF X2= 0 GOTOA 110
X2 X2+ 1 26X2 X2+ 1 26INSTRUCCION 1 #(I1)
...
INSTRUCCION k #(Ik)
Computa la funcion f2: N N
f2(x) = (1)P2
(x)
#(P2) =[109, 110, 26, 26, #(I1), . . . , #(Ik)]1
107
Teorema del ParametroHay un programa Px2 para la funcion fx2 (x1) = f(x1, x2)
La transformacion (x2, #(P))#(Px2 ) es p.r., es decir, existeuna funcion S: N2 Np.r. tal que dado x2 e y= #(P) calcula#(Px2 ):
S(x2, y) =
2109 3110
x2
j=1p26j+2
|y+1|
j=1pj+x2+2
(y+1)[j]
1
TeoremaHay una funcion p.r. S: N2 N tal que
(2)y (x1, x2) =
(1)S(x2,y)
(x1).
TeoremaPara cada n , m> 0 hay una funcion p.r. inyectiva Snm: N
n+1 Ntal que
(n+m)y (x1, . . . , xm, u1, . . . , un) =
(m)Snm(u1,...,un,y)
(x1, . . . , xm) 108
-
7/25/2019 Lgica y computabilidad
28/66
Programas autoreferentes
en la demostracion del Halting Problem construimos unprograma Pque, cuando se ejecuta con su mismo numero deprograma (i.e. #(P)), evidencia una contradiccion
en general, los programas pueden dar por supuesto queconocen su mismo numero de programa
pero si un programa Pconoce su numero de programa,podra, por ejemplo, devolver su mismo numero, i.e. #(P)
109
Teorema de la Recursion
TeoremaSig: Nn+1 Nes parcial computable, existe un etal que
(n)e (x1, . . . , xn) = g(e, x1, . . . , xn)
Demostracion.SeaS1n la funcion del Teorema del Parametro:
(n+1)y (x1, . . . , xn, u) =
(n)S1n(u,y)
(x1, . . . , xn).
La funcion (x1, . . . , xn, v)g(S1n(v, v), x1, . . . , xn) es parcialcomputable, de modo que existe dtal que
g(S1n (v, v), x1, . . . , xn) = (n+1)d (x1, . . . , xn, v)
= (n)
S1n(v,d)(x1, . . . , xn)
desta fijo; ves variable. Elegimos v= d y e= S1n(d, d). 110
Teorema de la Recursion
CorolarioSig: Nn+1 Nes parcial computable, existeninfinitose tal que
(n)e (x1, . . . , xn) = g(e, x1, . . . , xn)
Demostracion.
En la demostracion del teorema anterior, existeninfinitos d tal que
(n+1)d =g(S
1n (v, v), x1, . . . , xn).
vS1n (v, v) es inyectiva de modo que existen infinitos
e= S1n (d, d).
111
Quines
Unquinees un programa que cuando se ejecuta, devuelve comosalida el mismo programa.
Por ejemplo:
char*f="char*f=%c%s%c;main()
{printf(f,34,f,34,10);}%c";
main(){printf(f,34,f,34,10);}
112
-
7/25/2019 Lgica y computabilidad
29/66
Quines
Existeetal que e(x) = e?
S, el programa vaco tiene numero 0 y computa la funcionconstante 0, i.e. 0(x) = 0.
Proposicion
Hay infinitosetal quee
(x) = e.
Demostracion.Considerar la funcion g: N2 N, g(z, x) = z.Aplicando el Teorema de la Recursion, existen infinitos etal que
e(x) = g(e, x) = e.
113
Quines
No hay nada especial con que la salida del programa sea su propionumero en el resultado anterior. Funciona para cualquier h parcialcomputable.
Existeetal que e(x) = h(e)?
Proposicion
Hay infinitosetal quee(x) = h(e).
Demostracion.Considerar la funcion g: N2 N, g(z, x) = h(z).Aplicando el Teorema de la Recursion, existen infinitos etal que
e(x) = g(e, x) = h(e).
114
Teorema del Punto Fijo
TeoremaSif : N Nes computable, existe un etal quef(e)= e.
Demostracion.Considerar la funcion g: N2 N,
g(z, x) = f(z)(x).
Aplicando el Teorema de la Recursion, existe un etal que paratodo x,
e(x) = g(e, x) = f(e)(x)
115
EjercicioProbar que f : N N,
f(x) =
1 xes total
0 si no
no es computable.
Supongamos f computable. Puedo definir el siguiente programa P:
[A] IF f(X) = 1 GOTO A
Tenemos
(2)P (x, y) = g(x, y) =
xes total
0 si no
es parcial computable. Por el Teorema de la Recursi on, sea e talque e(y) = g(e, y). ees total g(e, y) para todo y e(y) para todo y
eno es total eno es total g(e, y) = 0 para todo y e(y) = 0 para
todo y ees total 116
-
7/25/2019 Lgica y computabilidad
30/66
ComputabilidadClase 7
Conjuntos c.e., teorema de la enumeracion, teorema de Rice yaplicaciones
117
Conjuntos en teora de la computabilidad
Cuando hablamos un conjunto de naturales A pensamos siempreen la funcion caracterstica de ese conjunto.
A(x) =
1 si x A
0 si no
As, un conjunto puede ser:
computable
primitivo recursivo
TeoremaSean A, Bconjuntos de una clase PRCC. EntoncesA B, A ByA estan en C.
118
Conjuntos computablemente enumerablesIgual que con las funciones hay conjuntos computables, por ejemplo
, N , {p: pes primo} hay conjuntos no computables, por ejemplo
{x, y: HALT(x, y)} , {x, y, z: x(y) = z}
DefinicionUn conjunto A es computablemente enumerable (c.e.)cuando
existe una funcion parcial computable g: N N tal que
A={x: g(x)} = dom g
podemos decidir algoritmicamente si un elementos pertenecea A, pero para elementos queno pertenecen a A, el algoritmose indefine
se llaman algoritmos desemi-decision: resuelven unaaproximacion al problema de decidir la pertenencia de unelemento al conjunto A
119
Propiedades de los conjuntos c.e.Un conjunto A es co-c.e. si A es c.e.
TeoremaSiA es computable entoncesA es c.e.
Demostracion.SeaPA un programa para [la funcion caracterstica de] A.Consideremos el siguiente programa P:
[C] IF PA(X) = 0 GOTO C
Tenemos
P(x) =
0 si x A
si no
y por lo tantoA={x: P(x)}
120
-
7/25/2019 Lgica y computabilidad
31/66
Propiedades de los conjuntos c.e.
TeoremaSiA yBson c.e. entoncesA B yA B tambien son c.e.
Demostracion.Sean A={x: p(x)} , B= {x: q(x)}
(A B) El siguiente programa Rcomputa A B:
Y p(x)
Y q(x)En efecto, R(x) sii p(x) y q(x).
(A B) El siguiente programa R computaA B:
[C] IF STP(1)(X, p, T) = 1 GOTOE
IF STP(1)(X, q, T) = 1 GOTO E
T T+ 1
GOTOC
En efecto, R(x) sii p(x) o q(x). 121
Propiedades de los conjuntos c.e.
TeoremaA es computable siiA yA son c.e.
Demostracion.
() si A es computable entonces A es computable
() supongamos que A y A son c.e.
A={x: p(x)} , A={x: q(x)}
ConsideremosP:
[C] IF STP(1)(X, p, T) = 1 GOTOF
IF STP(1)(X, q, T) = 1 GOTO E
T T+ 1
GOTOC
[F] Y 1
Para cada x, x A o bien x A. Entonces Pcomputa A.122
Teorema de la enumeracion
Definimos
Wn= {x: n(x)} = dominio del n-esimo programa
Teorema
Un conjuntoA es c.e. sii existe un n tal queA = Wn.
Existe una enumeracion de todos los conjuntos c.e.
W0, W1, W2, . . .
123
Problema de la detencion (visto como conjunto)Recordar que
Wn= {x: n(x)}
DefinimosK= {n: n Wn}
Observar que
n Wn sii n(n) s ii HALT(n, n)
TeoremaKes c.e. pero no computable.
Demostracion.
la funcion n (n, n) es parcial computable, de modo que Kes c.e.
supongamos que K fuera computable. Entonces K tambien losera. Luego existe un etal queK =We. Por lo tanto
e K sii e We sii e K124
-
7/25/2019 Lgica y computabilidad
32/66
Mas propiedades de los conjuntos c.e.
TeoremaSiA es c.e., existe un predicado p.r. R: N2 N tal que
A={x: (t) R(x, t)}
Demostracion.SeaA = We. Es decir,
A={x: e(x)}.
Entoncesx A cuando en algun tiempo t, el programae conentradax termina, i.e.
A={x: (t) STP(1)(x, e, t) R(x, t)
}
125
Mas propiedades de los conjuntos c.e.
TeoremaSiA = es c.e., existe una funcion p.r. f : N N tal que
A={f(0), f(1), f(2), . . . }
Demostracion.Por el teorema anterior, existe Pp.r. tal que
A={x: (t) P(x, t)}.
Seaa A y definamos
f(u) =
l(u) si P(l(u), r(u))
a si no
x A existe ttal que P(x, t) f(x, t) = x
sea xtal que f(u) = xpara algun u. Entonces x= a o bien ues de la forma u= x, t, con P(x, t). Luego x A. 126
Mas propiedades de los conjuntos c.e.
TeoremaSif : N Nes parcial computable, A ={f(x) : f(x)} es c.e.
Demostracion.Sea p= f y sea A ={f(x) : f(x)}. Definamos el programa Q
[A] IF STP(1)(Z, p, T) = 0 GOTO B
IF p(Z) = X GOTOE
[B] Z Z+ 1
IFZ T GOTOA
T T+ 1
Z 0
GOTOA
Notar que Q(X) si existenZ, Ttal que
Z T STP(1)(Z, p, T) es verdadero
(i.e. el programa para f termina
en To menos pasos con
entradaZ)
X= f(Z)
Q(x) =
0 si x A
si no
LuegoA es c.e. 127
Caracterizaciones de los conjuntos c.e.
TeoremaSiA =, son equivalentes:
1. Aes c.e.
2. Aes el rango de una funcion primitiva recursiva
3. Aes el rango de una funcion computable
4. Aes el rango de una funcion parcial computable
Demostracion.
(1 2) Teorema de hoja126
(2 3) Trivial
(3 4) Trivial
(4 1) Teorema de hoja127
128
-
7/25/2019 Lgica y computabilidad
33/66
Teorema de RiceA Nes un conjuntode ndices si existe una clase de funcionesN Nparciales computables Ctal que A ={x: x C}
TeoremaSiA es un conjunto de ndices tal que =A = N, A no escomputable.
Demostracion.SupongamosC tal que A ={x: x C} computable. Sean f C
y g / Cfunciones parciales computables.Seah : N2 N la siguiente funcion parcial computable:
h(t, x) =
g(x) si t A
f(x) si no
Por el Teorema de la Recursion, existe etal que e(x) = h(e, x).
e A e= ge / C e /A
e /A e= f e C e A129
Aplicaciones del Teorema de Rice
El teorema da una fuente de conjuntos no computables:
{x: xes total}
{x: x es creciente}
{x: x tiene dominio infinito}
{x: xes primitiva recursiva}
Todos son no computables porque todos son conjuntos de ndicesno triviales!
130
Ejemplos de conjuntos no c.e. K= {x: x(x)} no es c.e.
Kes c.e. de modo que si K lo fuera, Kser a computable Tot= {x: x es total} no es c.e.:
es una diagonalizacion simple. Supongamos que Totes c.e. existefcomputable tal que Tot= {f(0), f(1), f(2), . . . } entonces existe etal que e(x) = f(x)(x) + 1 como e es total, e Tot. De modo que existe utal que f(u) = e f(u)(x) = f(x)(x) + 1. Absurdo para x= u.
Tot= {x: xno es total} no es c.e. parecido a lo que hicimos la clase pasada. Supongamos Tot c.e. existed tal que Tot= dom d definimos el siguiente programa P:
[C] IF STP(1)(X, d, T) = 1 GOTO E
T T+ 1
GOTOC
sigue igual a lo que vimos la clase pasada
(2)P (x, y) = g(x, y) =
x es total
0 si no131
Conjuntos mas difciles que el halting problem
K= {x: x(x)} no es computable pero K es c.e.
Tot= {x: xes total}no es computable Totno es c.e. Totno es c.e.
de alguna forma, Totes mas dif cil que K esto se formaliza dentro de la teora no hay tiempo para verlo en esta materia pero lo estudiamos enTeora de la Computabilidad
se suele dar los primeros cuatrimestres da 3 puntos como optativa para la licenciatura y se cursa 1
vez por semana http://www.glyc.dc.uba.ar/teocomp/
132
-
7/25/2019 Lgica y computabilidad
34/66
ComputabilidadClase 8
Oraculos, reducibilidad de Turing, jerarqua aritmetica,
problema de Post
133
OraculosEl lenguaje S se extiende:
tiene entradas X1, . . . , Xn N(como antes) y una entradaespecial que se llama oraculo
en el oraculo no se pone un numero natural sino unconjunto
A N.
un nuevo termino para leer el oraculo seteado en A
ORACULO[i] =
1 si i A
0 s ino
Todo se puede aritmetizar como antes. Existe un programauniversal:
Ae(x1, . . . , xn) = salida del e-esimo programa
con entrada x1, . . . , xn y oraculo =A
134
Tienen mas poder de computo
Por ejemplo, hay un programa que calcula el halting problem
K ={x: x(x)}
Pero claro... con oraculo K.
Por ejemplo, hay un programa p tal que
Ap =A para todo A
Ap =A para todo A
Kp ={x: dom x= }
Sin embargo, hay problemas que no se pueden resolver aunteniendo el oraculo K:
{x: xes total}
{x: Kx(x)}
135
Reducibilidad de TuringPara A, B N, decimos que A T B cuando se puede calcular elconjuntoA con oraculo B, i.e. existe ptal que
Bp =A
o sea, para todo x N
Bp(x) = A(x) = 1 si x A
0 sino
Tambien se dice que A es B-computable
AT Apara todo A
AT Apara todo A
{x: dom x= } T K
{x: xes total} T K
{x: Kx(x)} T K
136
-
7/25/2019 Lgica y computabilidad
35/66
El saltoParaA Nse define elsalto de A como
A ={x: Ax(x)}
Por ejemplo,
={x: x(x)} ={x: x(x)} = K
={x:
x(x)}
={x:
x (x)}
(n) ={x: (n1)x (x)}
DecimosA
-
7/25/2019 Lgica y computabilidad
36/66
La jerarqua aritmetica Aes (n)-c.e. sii
existe etal que A = dom(n)
e existe Pp.r. tal que
A(x) = 1 sii (y)(z)(w) . . . P(x, y, z, w, . . . ) con nalternancias de cuantificadores (empezando con )
se los llama conjuntosn+1 Aes (n)-co-c.e. sii A es (n)-c.e. sii
existe etal que A = dom(n)
e existe Rp.r. tal que
A(x) = 1 sii (y)(z)(w) . . . R(x, y, z, w, . . . ) con nalternancias de cuantificadores (empezando con )
se los llama conjuntosn+1 Aes (n)-computablesii A T
(n) sii Aes (n)-c.e. y(n)-co-c.e. existenP y Rp.r. tal que
A(x) = 1 sii (y)(z)(w) . . . P(x, y, z, w, . . . )
sii (y)(z)(y) . . . R(x, y, z, w, . . . )
conn alternancias de cuantificadores. se los llama conjuntosn+1 141
La jerarqua aritmetica
1 1
1
2 2
2
...
142
Problema de Post
Ejemplos de conjuntos c.e.
K= {x: x(x)}T
T
{x, y: x(y)}T
{x: xes primo}T
{x, y, z: x(y) = z}T
N T {x: dom x=}T
{x: x(x) tarda mas de 10 pasos en terminar}T
{x: 0 dom x}T
DecimosA T Bcuando A T B y BT A.
Problema de Post (1944): Existe un A c.e. tal que
-
7/25/2019 Lgica y computabilidad
37/66
Materia optativa
Todo esto y mucho mas en...
Teora de la Computabilidad
se suele dar los primeros cuatrimestres
da 3 puntos como optativa para la licenciatura y se cursa 1vez por semana
http://www.glyc.dc.uba.ar/teocomp/
145
Logica ProposicionalClase 1
Lenguaje de logica proposicional, semantica, tautologa,
consecuencia semantica, conjunto satisfacible, sistemaaxiomatico SP, consecuencia sintactica
146
El lenguaje P
smbolos p ( )
p, p, p, p, . . . son smbolos prop osicionales
formulas
1. to do smbolo proposicional es una f ormula2. si es una formula entonces es una formula3. si y son formulas entonces ( ) es una formula4. nada mas es una formula
convenciones escribimos qpor p r porp sp orp... escribimos ( ) en lugar de ( ) escribimos ( ) en lugar de ( ) escribimos en lugar de () cuando convenga
llamamosPROPal conjunto de todos los smbolosproposicionales
llamamosFORMal conjunto de todas las formulas
147
SemanticaUnainterpretaciones una funcion
v : PROP {0, 1}
A vtambien se la llama valuacion.
Definimos la nocion deverdad de una formula para una valuacion.
Si FORM y ves una valuacion, notamos v|= si es verdadera para v
v|= si es falsa para v
La definicion de |= es recursiva:
1. si p PROP, v|=psii v(p) = 1
2. v|= sii v|=
3. v|= ( ) sii v|= o v|=
148
S i T l d d d i i
-
7/25/2019 Lgica y computabilidad
38/66
Semantica
Observar que, por la convencion,
5. v|= ( ) sii v|= y v|=
6. v|= ( ) sii v|= o v |=
Por ejemplo, si v(p) = 1 , v(q) = 0 , v(r) = 1
v|= (p r)
v|= (q r)
v|=p
v|= (p q)
149
Tautologas y metodo de decisionUna formula es unatautologa (|=) si es verdadera paratoda interpretacion, i.e. para toda valuacion v, v|=.
Proposicion
Sea FORMy sean v ywson dos valuaciones tal quev(p) = w(p)para toda variable proposicional que aparece en .Entoncesv|= siiw|=.
Existe unmetodo de decisi onpara saber si es tautologa o no:
supongamos que tiene variables proposicionales p1, . . . , pn seaP({p1, . . . , pn}) = {V1, . . . , V2n}
para i {1, . . . , 2n} definimos vi(p) =
1 si p Vi
0 si no
es tautologa sii
vi |= para todo i {1, . . . , 2n}
150
Consecuencia semantica y conjunto satisfacibleSea FORM y FORM
es consecuencia semantica de (|=) si para todainterpretacion v:
si v|= para toda lo notamos v|=
, entonces v |=
essatisfaciblesi existe una interpretacion vtal que v|= paratoda (i.e. tal que v|= )
Por ejemplo
{q} |=q
{q} |=p q
{r, p q} |=p
{r, p q} |=s
es satisfacible
{p, q}es satisfacible
{p, p q}no es satisfacible
{p, p q, q}no es satisfacible151
Algunos resultados sobre |=
Proposicion
1. |= sii|= (i.e. es tautologa)
2. si|= entonces |=
3. {} |=
4. si y |= entonces |=
5. si |= y |= entonces |=
Demostracion de 5.
sea vuna interpretacion tal que v|=
sabemos v|=
sabemos v|=
concluimos v|=
152
M i d d ti SP Ej l d t i d
-
7/25/2019 Lgica y computabilidad
39/66
Mecanismo deductivo SP
axiomas. Sean ,, FORM
SP1 ( )SP2 (( ))(()())SP3 ( )( )
regla de inferencia
MP Sean , FORM. es una consecuenciainmediata de y
Unademostracionde en SPes una cadena finita y no vaca
1, . . . , n
de formulas de Ptal quen= y
ies un axioma o
i es una consecuencia inmediata de k, l, k, l< i
En este caso, decimos que es unteorema()153
Ejemplo: demostracion de p p
Recordar
SP1 ( )
SP2 (( ))(() ())
SP3 ( )( )
MP Sean , FORM. es una consecuenciainmediata de y
Demostracion:
1. p ((p p) p) SP12. (p ((p p) p))((p (p p)) (p p)) SP23. (p (p p)) (p p) MP 1 y 24. p (p p) SP15. p p MP 3 y 4
Concluimos p p(i.e. p pes un teorema)
154
Consecuencia sintactica
Sea FORM y FORM
es unaconsecuencia sintacticade ( ) si existe una cadenafinita y no vaca
1, . . . , n
de formulas de Ptal quen= y
ies un axioma o i o
i es una consecuencia inmediata de k, l, k, l< i
Aqu, 1, . . . , n se llamaderivacionde a partir de . se llamateora. Decimos que es unteorema de la teora .
155
Correctitud de SP
TeoremaSi entonces |= (i.e. si es teorema de la teora , es validoen toda interpretacion de).
Demostracion.Supongamos . Es decir, existe una cadena finita y no vaca
1, . . . , n
de formulas de Ptal quen= y
ies un axioma o
i o
i es una consecuencia inmediata de k, l, k, l< i
Demostramos que |= por induccion en n (la longitud de lademostracion). Detalles a continuacion.
156
D t i d C tit d d SP Ej l
-
7/25/2019 Lgica y computabilidad
40/66
Demostracion de Correctitud de SP
Propiedad a demostrar:
P(n) = si1, . . . , n= es una derivacion de a partir deentoncesv|= v |=
Demostramos que vale P(n) p or induccion en n .
1. caso base.Veamos que vale P(1). Sup. vtal que v|= . Queremosver que v|= v|=. Hay 2 posibilidades1.1 is axioma de SP: en este caso, v|=;
1.2 : en es te caso, tambien v|=.2. paso inductivo.Sup. v tal que v|= . Sup. que vale P(m) para todo
m n. Queremos ver que vale P(n+ 1).Sup. 1, . . . , n, n+1= es una derivacion de a partir de . Hay 3 posibilidades
2.1 is axioma de SP: igual que en caso base;2.2 : igual que en caso base;2.3 es consecuencia inmediata de i y j= i (i,j n). Por HI
(P(i) y P(j)), sabemos v|=i y v|=i . Entoncesnecesariamente v|=.
157
Ejemplos 1= {p} p
1. p p 1
2= {p} p1. p p 22. p ( p) SP13. p MP 1 y 2
3= {p} q
porque 3|=q(considerar v(p) = 1; v(q) = 0)
4= {p, p} 1. p ( p) SP12. p p 43. p MP 1 y 24. ( p)(p ) SP35. p MP 3 y 46. p p 47. MP 5 y 6
158
Conjuntos y sistemas consistentes FORM esconsistentesi no existe FORM tal que
y
Un sistema S esconsistentesi no existe FORM tal que
S y S
TeoremaEl sistema SP es consistente.
Demostracion.
sea vcualquier valuacion
por correctitud, todo teorema de SPes verdadero para v
v|= v|=
luego no puede pasar que y sean teoremas
159
Algunos resultados sobre
Proposicion
1. sii (i.e. es teorema)
2. si entonces
3. {}
4. si y entonces 5. si y entonces
Si reemplazamos por |=, obtenemos los mismos resultados (verhoja152)
160
Res men Notas sobre comp tabilidad
-
7/25/2019 Lgica y computabilidad
41/66
Resumen
lenguajeP
semantica
tautologa(verdadera en toda interpretacion)
consecuencia semantica|=
conjunto satisfacible(existe modelo para todos sus elementos)
metodo deductivo
teorema(tiene demostracion en SP)
consecuencia sintactica
conjunto consistente(no permite probar y )
161
Notas sobre computabilidadSe pueden codificar las formulas de Pcon numeros naturales. a cada formula se le asigna un numero # > 0 cada numero positivo representa una unica formula
Se puede decidir algortmicamente si una formula es un axioma ono es computable la funcion
ax(x) = 1 si la formula de numeroxes un axioma de SP0 si noSe puede decidir algortmicamente si una formula es consecuenciainmediata de otras dos es computable la funcion
mp(x, y, z) =
1 si la formula de numerozes consecencia
inmediata de las formulas de numerosx e y
0 si no162
Notas sobre computabilidad
Las demostraciones son listas (finitas) de formulas.
la demostracion 1. . . n se codifica como [#1, . . . , #n]
Se puede decidir algortmicamente si una lista de formulas es unademostracion valida o no
es computable la funcion
dem(x) =1 x es una demostracion valida
0 si no
en efecto,
dem(x) = (k {1, . . . , |x|})[ax(x[k]) cons(x, k)]
cons(x, k) = (i,j {1, . . . , k 1})[mp(x[i], x[j], x[k])]
163
Notas sobre computabilidad considerar el siguiente programa P:
[A] IF dem(D) = 1 D[|D|] = X GOTO E
D D+ 1
GOTOA
Pbusca una demostracion para la formula con numeroX
si la encuentra, se detiene si no, se indefine
sii P(#), o equivalentemente
es teorema sii # domP
el conjunto de teoremas de SPes c.e. esto pasa en general para cualquier sistema axiomatico
es decir, cualquier sistema de deduccion con un conjuntocomputable de axiomas y reglas de inferencia computablestiene un conjunto de teoremas c.e.
sera computable el conjunto de teoremas de SP? 164
Plan
-
7/25/2019 Lgica y computabilidad
42/66
Logica ProposicionalClase 2
Teorema de la deduccion, lema de Lindenbaum, completitud de
SP, compacidad
165
Plan
vimos queSPes correcto: |=Esto prueba
satisfacible consistente
ahora veremos que SPes completo: |=
Para esto: Lema de Lindenbaum satisfacible consistente
consecuencia: Teorema de Compacidad
166
El Teorema de la Deduccion
TeoremaSi {} entonces
Demostracion.Por induccion en la longitud de la demostracion de {} .Supongamos que
1, . . . , n
es una derivacion de (= n) a partir de {}. caso base (n= 1)
paso inductivo
HI: para toda derivacion de a partir de {} de longitud
-
7/25/2019 Lgica y computabilidad
43/66
Demostracion del Teorema de la Deduccion (paso inductivo)Supongamos
1, . . . , n
es una derivacion de a partir de {}
HI: para toda derivacion de a partir de {} de longitud < ntenemos
Queremos ver que . Hay 4 posibilidades:
1. es un axioma de SP: igual que en en caso base2. : igual que en en caso base3. = : igual que en en caso base4. se infiere por MP de i yj (i,j< n)
sin perdida de generalidad, j= i {} iy la derivacion tiene longitud < n por HI i {} jy la derivacion tiene longitud < n por HI j, i.e. (i ) sabemos (SP2) ( (i ))(( i) ()) por MP 2 veces 169
Conjuntos consistentes
Proposicion
1. {} es inconsistente sii
2. {} es inconsistente sii
Demostracion de 1.
() {}
trivialmente {} {} es inconsistente() existe tal que {} y {}
por el Teorema de la Deduccion,
y
se puede ver que (ejercicio)()(( ))por MP 2 veces tenemos
170
Satisfacible consistente
TeoremaSi FORM es satisfacible entonces es consistente.
Demostracion.
supongamos vtal que v|= pero es inconsistente
existe tal que y
por correctitud de SP, |= y |=
v|= y v|=
171
Lema de Lindenbaum
FORM esmaximal consistente (m.c.)en SP si
es consistente y para toda formula
o
existe tal que {} y {}
LemaSi FORM es consistente, existe m.c. tal que .
172
Demostracion del Lema de Lindenbaum (obtener m c ) Conjuntos maximales consistentes
-
7/25/2019 Lgica y computabilidad
44/66
Demostracion del Lema de Lindenbaum (obtener m.c.)Enumeramos todas las formulas:1, 2, . . . Definimos 0=
n+1=
n {n+1} si n {n+1}es consistente
n si no =
i0i
Tenemos
1.
2. cada i es consistente3. es consistente
si no, existe tal que y en ambas derivaciones aparecen unicamente {1, . . . , k} . seajsuficientemente grande tal que {1, . . . , k} j entonces j y j ; contradice 2
4. es maximal supongamos /. Debe existirn tal quen+1= n+1 /n+1, entonces n {n+1} es inconsistente luego {n+1} es inconsistente (pues n)
173
Conjuntos maximales consistentes
Proposicion
Si es m.c. entonces para toda FORM, o bien o bien.
Demostracion.
no puede ser que y esten en porque sera inconsistente
supongamos que ninguna esta. Como es maximal y por
Proposicion de la hoja170,
{}es inconsistente {} es inconsistente
inconsistente
Proposicion
Sea m.c. sii .174
Consistente satisfacible
TeoremaSi FORM es consistente entonces es satisfacible.
Demostracion.Dado consistente, construimos m.c. (Lindenbaum)
Definimos la interpretacion vtal que
v(p) =1 sii p
Veamos v|= sii por induccion en lacomplejidadde (i.e. cantidad de o que aparecen en )
caso base: = p. Trivial por definicion de v.
paso inductivo:HI:v|= sii para toda de complejidad < mSea de complejidad m . Hay 2 casos:
1. =2. = 175
Demostracion de consistente satisfacible (caso =)
HI: v |= sii para toda de complejidad < m
= tiene complejidad m .
Quiero probar que v|= sii
() v|= v|= HI /
() / HIv|= v |= v|=
176
Demostracion de consistente satisfacible (caso = ) Teorema de Completitud (fuerte)
-
7/25/2019 Lgica y computabilidad
45/66
Demostracion de consistente satisfacible (caso = )HI:v |= sii para toda de complejidad< m= tiene complejidad m .Quiero probar que v|= sii
() v|= v|= ( ) v|= o v|=
v|= HI /
sabemos ( ) (ejercicio)por MP entonces
v|= HI sabemos por SP1 que ( )por MP entonces
() v|= v|= y v|= HI y /
y y sabemos ( ( )) (ejercicio)aplicando MP 2 veces, ( )por lo tanto ( )
entonces / 177
Teorema de Completitud (fuerte)
Probamos que
consistente sii satisfacible (hojas171 y 175)
{} es inconsistente sii (hoja170)
TeoremaSi |= entonces .
Demostracion.
supongamos |=
{} es insatisfacible
{} es inconsistente
178
Consecuencias del Teorema de Completitud
Corolario sii |=
Corolario sii|= (i.e. es un teorema deSPsi i es tautologa)
Teorema (Compacidad)
Sea FORM. Si todo subconjunto finito de es satisfacible,entonces es satisfacible.
Demostracion. supongamos insatisfacible
es inconsistente
existe tal que y
se usan solo finitos axiomas de
existe finito tal que y
es inconsistente
es insatisfacible 179
Resumen
lenguajeP
semantica
tautologa(verdadera en toda interpretacion)
consecuencia semantica|=
conjunto satisfacible(existe modelo para todos sus elementos)
metodo deductivo
teorema(tiene demostracion en SP)
consecuencia sintactica
conjunto consistente(no permite probar y )
180
Notas sobre computabilidad
-
7/25/2019 Lgica y computabilidad
46/66
Notas sobre computabilidad
Habamos visto que el conjunto de teoremas de SP es c.e.
Vemos que, de hecho, es computable:
metodo de decision = tablas de verdad
sii |=
sii en la tabla de verdad de solo hay 1s en la ultima columna
181
Logica de Primer OrdenClase 1
Lenguaje de logica de primer orden, terminos, formulas,
variables libres y ligadas, interpretacion, valuacion, niveles deverdad, consecuencia semantica
182
Lenguajes de primer orden
s mbolos logicos y auxiliares: x ( )
x, x, x, x, . . . son variables
VARes el conjunto de variables
se llamacuantificador universal
smbolos de cada lenguaje particular L =C F P , donde
Ces un conjunto de smbolos de constantes (puede ser C= ) Fes un conjunto de smbolos de funciones (puede ser F= ) Pes un conjunto de smbolos de predicados(P =)
183
Terminos
Para un lenguaje fijo L, definimos losterminos de L:
1. toda variable es un termino
2. todo smbolo de constante deL es un termino
3. si fes un smbolo de funcion n-adico de L y t1, . . . , tn sonterminos de L, entonces f(t1, . . . , tn) es un termino de L
4. nada mas es un termino de L
TERM(L)es el conjunto de todos los terminos del lenguajeL
Un termino es cerradosi no tiene variables.
Por ejemplo, para L =C F P , con C= {c, d}, F= {f} yP= {R} (fde aridad 3, R binario)son terminos:
c , d , x , f(c, d, x) , f(c, f(x, x, x), x)
184
Formulas Convenciones
-
7/25/2019 Lgica y computabilidad
47/66
FormulasPara un lenguaje fijo L, definimos lasformulas deL:
1. si Pes un smbolo de predicado n-adico de L y t1, . . . , tn sonterminos de L, entonces P(t1, . . . , tn) es una formula deL(atomica)
2. si es una formula de L entonces es una formula deL
3. si y son formulas deL entonces () es una formuladeL
4. si es una formula de L y xuna variable entonces (x) esuna formula deL
5. nada mas es una formula deL
FORM(L)es el conjunto de todas las formulas del lenguaje L
Por ejemplo, para L =C F P , con C= {c, d}, F= {f} yP= {R} (fde aridad 3, R binario)son formulas:
R(d, x) , (x) R(d, x) , (x) R(f(x, x, x), d)
185
Convenciones
usamos x, y, z, . . . para variables
usamos a, b, c, d, . . . para smbolos de constante
usamos f, g, h, . . . para smbolos de funcion (la aridadsiempre va a quedar clara del contexto)
usamos P, Q, R, . . . para smbolos de predicado (la aridad
siempre va a quedar clara del contexto) escribimos (x) en lugar de (x)
escribimos ( ) en lugar de ()
escribimos ( ) en lugar de( )
escribimos en lugar de () cuando convenga
186
Variables libres y ligadas unaaparicionde una variable xen una formula estaligadasi
esta dentro del alcance de un cuantificador. En caso contrario,dicha aparicion estalibre.
una variable esta libreen una formula si todas sus aparicionesestan libres.
una variable estaligadaen una formula si todas susapariciones estan ligadas.
una formula es unasentenciasi todas las variables son ligadas
(es decir, no hay apariciones libres de variables)Por ejemplo, (para un lenguaje con un smbolo de predicado binario P) en P(x, y) , x esta libre en (y) P(x, y) , xesta libre en (x) P(x, y) , x esta ligada en (x)(y) P(x, y) , x esta ligada en P(x, y)(x)(y) P(x, y)
la primera aparicion de xes ta libre la segunda aparicion de xesta ligada entonces, xno esta ni libre n i ligada 187
Interpretacion de un lenguaje
UnaL-estructuraA de un lenguaje L =C F P es
un conjunto A no vaco, se lo llama universoo dominio
las siguientes asignaciones:
para cada s mbolo de constante c C, un elemento fijo
cA A
para cada s mbolo de funcion n-aria f F, una funcion
fA : An A
para cada s mbolo de predicado n-ario P P, una relacion
PA An
Las funciones fA y predicados PA son siempre totales.
188
Ejemplos No ejemplos
-
7/25/2019 Lgica y computabilidad
48/66
Ejemplos
ParaL =C F P , con C= {c, d}, F= {f, g} y P= {P}(f unaria, g binaria, P binario)
L-estructuraA
A= Z
cA= 0 dA= 1 fA(x) = x gA(x, y) = x+ y PA(x, y) sii x divide a y
L-estructuraB
B= P(N)
cB = dB = N fB(x) = x gB(x, y) = x y PB(x, y) sii x y
189
No ejemplos
ParaL =C F P , con C= {c, d}, F= {f, g} y P= {P}(f unaria, g binaria, P binario)
L-estructuraM
M= Z cM= 0 d
M= 1
fM(x) = 1/x gM(x, y) = xy
PM(x, y) sii xdivide a y
en general
1/x / Z
xy / Z
L-estructuraN
N= funciones R R cN= funcion identidad dN= funcion 0 fN(x) = derivada de x gN(x, y) = x y PN(x, y) sii x= y
una funcion R Rpuede noser derivable
190
ValuacionesFijemos una L-estructuraA con dominio A.
Unavaluacionpara A es una funcion v: VAR A
Extendemosv a v: TERM(L) A, que interpreta un termino ten unaL-estructuraA:
si t= x(variable) entonces
v(t) = v(x)
si t= c (constante) entonces
v(t) = cA
si t= f(t1, . . . , tn) (funcion) entonces
v(t) = fA(v(t1), . . . ,v(tn))
Seav una valuacion deA y sea a A. Definimos la valuacionv(x= a) de la siguiente manera
v(x= a) (y) =
v(y) x=y
a x= y191
EjemplosParaL =C F P , con C= {c, d}, F= {f, g} y P= {P}(f unaria, g binaria, P binario)
L-estructuraA
A= Z cA= 0 dA= 1 fA(x) = x g
A(x, y) = x+ y
PA(x, y) sii x divide a y
Tenemos
si v(x) = 2
v
g(x, f(d))
= 2+(1) = 1
para cualquier v
v
g(c, f(d))
= 0+(1) =1
L-estructuraB
B= P(N) cB = dB = N fB(x) = x g
B(x, y) = x y
PB(x, y) sii x y
Tenemos
si v(x) = {1, 2}
v
g(x, f(d))
={1, 2}N ={1, 2}
para cualquier v
v
g(c, f(d))
= N =192
Interpretacion de una formula Ejemplos
-
7/25/2019 Lgica y computabilidad
49/66
Interpretacion de una formulaSeaA una L-estructura con dominio A y v una valuacion de A.Definimos cuando es verdadera en A bajo la valuacion v(notacion:A |=[v])
1. es de la forma P(t1, . . . , tn) (atomica)
A |=P(t1, . . . , tn)[v] sii
v(t1), . . . ,v(tn)
PA
2. es de la forma
A |=[v] sii noA |=[v]
3. es de la forma ( )
A |= ( )[v] sii no A |=[v] o A |=[v]
4. es de la forma (x)
A |= (x)[v] sii para cualquiera A, A |=[v(x= a)]
193
EjemplosParaL =C F P , con C= {c, d}, F= {f, g} y P= {P}(f unaria, g binaria, P binario)
L-estructuraA
A= Z cA= 0 dA= 1 fA(x) = x gA(x, y) = x+ y PA(x, y) sii x divide a y
Tenemos
para v(x) = 1A |=P(x, d)[v]
para v(x) = 0A |=P(x, c)[v]
para cualquier vA |= (y)P(y, g(y, d))[v]
L-estructuraB
B= P(N) cB = dB = N fB(x) = x gB(x, y) = x y PB(x, y) sii x y
Tenemos
para v(x) = B |=P(x, d)[v]
para v(x) = {1, 2, 3}B |=P(x, c)[v]
para cualquier vB |= (y)P(y, g(y, d))[v]
194
Notacion (,,)
SeaA una L-estructura y v una valuacion deA. Se deduce:
5. es de la forma ( )
A |= ( )[v] sii A |=[v] o A |=[v]
6. es de la forma ( )
A |= ( )[v] sii A |=[v] y A |=[v]
7. es de la forma (x)
A |= (x)[v] sii hay una A tal que A |=[v(x= a)]
195
3 niveles de verdad
Para un lenguaje L fijo.
1. es satisfaciblesi existe una L-estructuraA y una valuacionv deA tal que A |=[v]
2. es verdadera (o valida) en una L-estructuraA (A |=)si
A |=[v] para toda valuacion v de A decimos queA es unmodelode
3. es universalmente valida (|=)si A |=[v] para todaL-estructuraA y toda valuacion v deA
196
Ejemplos Algunos resultados sobre satisfacibilidad y validez
-
7/25/2019 Lgica y computabilidad
50/66
j p A=Z;
-
7/25/2019 Lgica y computabilidad
51/66
g j gL es un lenguaje con igualdad si tiene un smbolo proposicionalbinario especial (el =) que solo se interpreta como la igualdad.
Fijemos un lenguaje L con igualdad y con ningun otro smbolo.Buscamos FORM(L) tal que {A : A |=} sea la clase demodelos
con exactamente 1 elemento
= (x)(y)x= y
con exactamente 2 elementos
= (x)(y) x=y
x=y(z)(z= x z= y)
con al menos 3 elementos
= (x)(y)(z)
x=y x=z y=z
con infinitos elementos... con finitos elementos. Se podra?201
Logica de Primer OrdenClase 2
Lema de sustitucion, sistema axiomatico SQ, consecuencia
sintactica, teorema de la generalizacion, teorema de lageneralizacion en constantes
202
Reemplazo de variables libres por terminos
SeaL =C F P un lenguaje fijo.
Sea FORM(L), t TERM(L) y x VAR. [x/t]es laformula obtenida a partir de sustituyendo todas las aparicioneslibres de la variable x por t
Por ejemplo, (para un lenguaje con smbolo de predicado binario P ysmbolo de funcion unario f)
P(x, y)[x/f(z)] = P(f(z), y) P(x, y)[x/f(x)] = P(f(x), y)
(x)(y) P(x, y)
[x/f(z)] = (x)(y) P(x, y)
P(x, y)(x)(y) P(x, y)
[x/f(z)] =
P(f(z), y)(x)(y) P(x, y)
Sic C, [c/t]es la formula obtenida a partir de sustituyendotodas las apariciones de la constante c por t
203
Variable reemplazable por un termino
Seat TERM(L), x VAR, FORM(L).
Decimos que x esreemplazablepor ten cuando
1. tes un termino cerrado (i.e. no tiene variables) o
2. ttiene variables pero ninguna de ellas queda atrapada por uncuantificador en el reemplazo [x/t]
Por ejemplo, (para un lenguaje con smbolo de predicado unario Pysmbolo de funcion binaria f)
En(y)
(x)P(x) P(x)
x es reemplazable por z: (y)
(x)P(x) P(z)
x es reemplazable por f(x, z): (y)
(x)P(x) P(f(x, z))
xno es reemplazable por f(x, y): (y)
(x)P(x) P(f(x, y))
204
Lema de Sustitucion Lema de Sustitucion
-
7/25/2019 Lgica y computabilidad
52/66
LemaSixes reemplazable porten entonces
A |= ([x/t])[v] sii A |=[v(x= v(t))]
Demostracion.Por induccion en la complejidad de.
(a veces escribo v por v) = P(u) es atomica (u es termino; el caso n-ario es similar).
A |=P(u[x/t])[v] sii v(u[x/t]) PA sii (lema auxiliar)v[x= v(t)](u) PA sii A |=[v(x= v(t))].
es de la forma o de la forma . Directo.
(sigue )
205
Demostracion (cont.) es de la forma (y) .
Sup. xno aparece libre en . Entonces v y v[x= v(t)] coinciden en todas lasvariables que aparecen libres en . Ademas, = [x/t]. Inmediato.
Sup. xaparece libre en . Como xes reemplazable por ten , yno ocurre en t.Luego para todo d A,
v(t) = v(y= d)(t). (1)
Ademas, xes reemplazable por ten . Como x=y,
[x/t] = ((y) )[x/t] = (y) ([x/t]).Luego
A |=[x/t][v] sii (def.) para todod A,A |=[x/t][v(y= d)]
sii (HI) para todo d A,A |=[v(y= d) w
(x= w(t))]
sii (1) para to do d A,A |=[v(y= d)(x= v(t))]
sii (x=y) para todo d A,A |=[v(x= v(t))(y= d)]
sii (def.) A |=[v(x= v(t))] 206
Mecanismo deductivo SQ(para un lenguaje fijo L)
Para un lenguaje fijo L