Práctica3

Vista previa del material en texto

Lógica y Computabilidad
Práctica 3: Funciones no-computables y conjuntos C.E.
2do cuatrimestre 2022
Ejercicio 1
a)
f1px, yq “
#
1 si Φ
p1q
x pyq Ó
0 si no
Suponemos que f1 es computable, y por lo tanto existe un programa P1 que la computa.
Definimos gpxq “ f1px, xq “
#
1 si Φ
p1q
x pxq Ó
0 si no
Sea Q un programa que computa g:
X2 Ð X1 (macro computable)
P1
Como asumimos que f1 es computable, g también lo es pues f1 computable ñ g computable.
Definimos ahora un programa Q1 tal que ΨQ1pxq “
#
0 si Φ
p1q
x pxq Ò
Ò si no
Q
[R] IF Y ‰ 0 GOTO R
Veamos que @x : Φ
p1q
#pQ1qpxq Ó ðñ ΨQ1pxq Ó ðñ ΨQpxq “ 0 ðñ gpxq “ 0 ðñ Φ
p1q
x pxq Ò
Sea e “ #pQ1q y tomando x “ e vemos que: Φ
p1q
e peq Ó ðñ Φ
p1q
e peq Ò Absurdo
Llegamos al absurdo por suponer que f1 era computable. Por lo tanto, f1 no es computable.
b)
f2px, yq “
#
1 si Φ
p1q
x pyq “ 0
0 si no
Suponemos que f2 es computable, y por lo tanto existe un programa P2 que la computa.
Definimos gpxq “ f2px, xq “
#
1 si Φ
p1q
x pxq “ 0
0 si no
Sea Q un programa que computa g:
X2 Ð X1 (macro computable)
P2
1
Como asumimos que f2 es computable, g también lo es pues f2 computable ñ g computable.
Definimos ahora un programa Q1 tal que ΨQ1pxq “
#
0 si Φ
p1q
x pxq ą 0_ Φ
p1q
x pxq Ò
Ò si no
Q
[R] IF Y ‰ 0 GOTO R
Veamos que @x : Φ
p1q
#pQ1qpxq Ó ðñ ΨQ1pxq Ó ðñ ΨQpxq “ 0 ðñ gpxq “ 0 ðñ Φ
p1q
x pxq ą 0_ Φ
p1q
x pxq Ò
Sea e “ #pQ1q y tomando x “ e vemos que: Φ
p1q
e peq Ó ðñ Φ
p1q
e peq ą 0_ Φ
p1q
e peq Ò
Analizamos cada caso:
Φ
p1q
e peq Ó ðñ Φ
p1q
e peq ą 0 Absurdo pues Φ
p1q
e peq Ó ðñ Φ
p1q
e peq “ 0 (por definición)
Φ
p1q
e peq Ó ðñ Φ
p1q
e peq Ò Absurdo
Llegamos al absurdo por suponer que f2 era computable. Por lo tanto, f2 no es computable.
c)
f3px, y, zq “
#
1 si Φ
p1q
x pyq Ó ^ Φ
p1q
x pyq ą z
0 si no
Suponemos que f3 es computable, y por lo tanto existe un programa P3 que la computa.
Definimos gpxq “ f3px, x, 0q “
#
1 si Φ
p1q
x pxq Ó ^ Φ
p1q
x pxq ą 0
0 si no
Sea Q un programa que computa g:
X2 Ð X1 (macro computable)
X3 Ð 0 (macro computable)
P3
Como asumimos que f3 es computable, g también lo es pues f3 computable ñ g computable.
Definimos ahora un programa Q1 tal que ΨQ1pxq “
#
1 si Φ
p1q
x pxq Ò _ Φ
p1q
x pxq “ 0
Ò si no
Q
[R] IF Y ‰ 0 GOTO R
Y Ð 1 (macro computable)
Veamos que @x : Φ
p1q
#pQ1qpxq Ó ðñ ΨQ1pxq Ó ðñ ΨQpxq “ 0 ðñ gpxq “ 0 ðñ Φ
p1q
x pxq Ò _ Φ
p1q
x pxq “ 0
Sea e “ #pQ1q y tomando x “ e vemos que: Φ
p1q
e peq Ó ðñ Φ
p1q
e peq Ò _ Φ
p1q
e peq “ 0
Analizamos cada caso:
Φ
p1q
e peq Ó ðñ Φ
p1q
e peq “ 0 Absurdo pues Φ
p1q
e peq Ó ðñ Φ
p1q
e peq “ 1 (por definición)
Φ
p1q
e peq Ó ðñ Φ
p1q
e peq Ò Absurdo
Llegamos al absurdo por suponer que f3 era computable. Por lo tanto, f3 no es computable.
d)
f4pxq “
#
1 si Φ
p1q
x pxq Ó ^ Φ
p1q
x pxq ‰ x
0 si no
2
Suponemos que f4 es computable, y por lo tanto existe un programa P4 que la computa.
Definimos ahora un programa Q tal que ΨQpxq “
#
0 si Φ
p1q
x pxq Ò _ Φ
p1q
x pxq “ x
Ò si no
P4
[R] IF Y ‰ 0 GOTO R
Veamos que @x : Φ
p1q
#pQqpxq Ó ðñ ΨP4pxq “ 0 ðñ f4pxq “ 0 ðñ Φ
p1q
x pxq Ò _ Φ
p1q
x pxq “ x
Sea e “ #pQq y tomando x “ e vemos que: Φ
p1q
e peq Ó ðñ Φ
p1q
e peq Ò _ Φ
p1q
e peq “ e
Analizamos cada caso:
Φ
p1q
e peq Ó ðñ Φ
p1q
e peq “ e Absurdo pues Φ
p1q
e peq Ó ðñ Φ
p1q
e peq “ 0 ‰ e pues Q no es el programa vaćıo
Φ
p1q
e peq Ó ðñ Φ
p1q
e peq Ò Absurdo
Llegamos al absurdo por suponer que f4 era computable. Por lo tanto, f4 no es computable.
3