Práctica 3 (LyC Verano)

De Cuba-Wiki

Ejercicios

Ejercicio 1

Sea f: N -> N computable.

Item A

Demostrar que la función

g(x) = min {y : f(y) = x}  si existe y tal que f(y) = x
       se cuelga           si no

es parcialmente computable.

Solución

Damos un programa que computa g.

Z1 <- X1
[A] Z3 <- f(Z2)  //Dado que f es computable, supongo que tengo el progama homónimo que la calcula, 
                 //y además sé que no se cuelga.
IF Z3 = Z1 GOTO B
Z2 <- Z2 + 1
GOTO A
[B] Y <- Z2

La idea es sencillamente chequear si f(y) = x, empezando con y = 0 e incrementando de a uno. Si en algún momento esto ocurre, ese y es el que busca la minimización de la primer rama de g. Si no ocurre nunca, el programa sigue incrementando el valor chequeado infinitamente, o sea se cuelga.


Item B

Demostrar que si f es además biyectiva, f^-1 es computable.

Solución

Notar que el programa que dimos computa f^-1. Como f es biyectiva, es inyectiva. Esto asegura que el resultado de la expresión min{y:f(y) = x} devuelve no sólo el mínimo y, sino el único. Además, la sobreyectividad nos asegura la existencia de tal y, con lo cual el programa no puede colgarse.

Ejercicio 2

Sea f: N -> N una función computable y sobreyectiva. Probar que existe una función computable e inyectiva g: N -> N tal que g(f(x)) <= x para todo x perteneciente a N.

Solución

Es casi el mismo problema que en el ejercicio 1. Podríamos ver a g como una especie de generalización de f^-1. Si f es inyectiva y sobreyectiva (i.e. biyectiva) se puede definir una f^-1 tal que f^-1(x) = g(f(x)) = x, para todo x natural.

Si debilitamos la hipótesis sobre f, y sólo pedimos que sea sobreyectiva, pasa a haber más de un xi tal que g(f(xi)) = x. Pero siempre habrá un único x1 tal que g(f(x1)) = x y además x1 es más chico que todos los xi. Este x1 se encuentra con la minimización:

min{y : f(y) = x}

Por otra parte, esta minimización es computable, dado que está garantizado por la sobreyectividad de f la existencia de al menos un y que verifique f(y) = x. Nuevamente, esta función se computa con el programa del ejercicio 1, item A. Por último, g es inyectiva porque en la expresión f(y) = x, dos valores x1 y x2 distintos no pueden provenir del mismo y, dado que esto violaría la definición de función.

Ejercicio 5

Probar que la siguiente función es primitiva recursiva:

f(x) = 1 si x = <<a,b>,c> y fi(b,a) termina en menos de c pasos
       0 en otro caso

Solución

f(x) es pr porque tanto los valores que devuelve como las funciones utilizadas en las guardas lo son. La decodificación de x en a, b y c es pr. y el predicado "fi(b,a) termina en menos de c pasos" es computado por el programa STP(b,a,c), que es pr.


Ejercicio 6

Decimos que una funcion parcialmente computable f es extensible si existe g computalbe tal que g(x) = f(x) para todo x en el dominio de f. Probar que existe una funcion f parcialmente computable que no es extensible.


Ejercicio 10

Probar que las siguientes funciones no son computables

Item A

f(x) = 1  si 
       0  si no

Supongo f es computable, por ende es total

Sea g(x,y) tal que

g(x,y) = 2x+1  si f(x)
         2x    si no

Por teorema de la recursion,

Supongo

Supongo

Absurdo que proviene de suponer que f es computable

Todos los items siguientes se resuelven con el mismo mecanismo

Item B

f(x) = 1  si 
       0  si no

Supongo f es computable

Sea g(x,y) tal que

g(x,y) = 1  si f(x)
           si no

Por teorema de la recursion,

Evaluando g en e se llega al absurdo

Item C

f(x,y) = 1  si 
         0  si no

Supongo f es computable, por ende tambien total

Sea g(x,y) tal que

g(x,y) =   si f(x,y)
           si no

Por teorema de la recursion,

Sea a tal que

Por teorema del parametro,

Evaluando g en (s,a) se llega al absurdo

Item D

f(x) = 1  si  es infinita
       0  si no

Supongo f es computable, por ende tambien es total

Sea g(x,y) tal que

g(x,y) = 0  si f(x)
         y  si no

Por teorema de la recursion,

Supongo ,

Supongo ,

Item E

f(x) = 1  si 
       0  si no

La condicion equivale a decir que

Supongo f es computable, por ende tambien es total

Sea g(x,y) tal que

g(x,y) =   si f(x)
         0  si no

Por teorema de la recursion,

Evaluando g en (e,y) para todo y, se llega al absurdo


Ejercicio 14

Probar que si B es re y f es una funcion parcialmente computable, entonces es re.


Como B es re, existe g parcialmente computable tal que

Para que A sea re, tiene que existir una funcion h parcialmente computable tal que .

Sea h = g(f(x)), parcialmente computable por ser composicion de pc.

Entonces A es re.

Ejercicio 17

Definir un predicado pr P tal que no sea re.

Ejercicio 20

Demostrar que las funciones definidas en el Ejercicio 10 no son computables aplicando el Teorema de Rice

Item C

f(x,y) = 1  si 
         0  si no

A = {x: }

Quiero ver que A no es computable por Rice. Para esto tengo que probar que:

1. A !=

A representa el conjunto de los programas que computan el programa 0 (aquel que devuelve 0 para toda entrada).

Ejemplo: el programa que computa f(x,y) donde

f(x,y) = (x>y).(y-x)+(x<=y).(x-y)

claramente, esta función hace lo mismo que #P=0 donde P es el programa que computa a

n(x) = 0

Entonces, A !=

2. A != N

Ejemplo: el programa que computa la función constante

g(x) = 8

Además, puede verse que hay programas que no están en A

Entonces, A != N

3. A es un conjunto de índices

Se dice que A es un conjunto de índices si dado C una clase de funciones parcialmente computables A es el conjunto de los programas que computan a dichas funciones. En este caso, A es el conjunto de los programas que computan lo mismo que (la función nula). Entonces dado x perteneciente a A y --> y pertenece a A.

Muy bien, ahora, por Rice, A no es computable

Supongo f computable. Entonces f(x,0) es computable. Pero f(x,0) = g(x) es la función característica de A. Absurdo, porque A no es computable --> f no es computable :)

El resto sale de la misma forma :)