Diferencia entre revisiones de «Práctica 3 (LyC Verano)»

De Cuba-Wiki
Sin resumen de edición
(→‎Ejercicio 17: Resolución)
(No se muestra una edición intermedia del mismo usuario)
Línea 14: Línea 14:
es parcialmente computable.
es parcialmente computable.


==== Solución ====
'''Solución'''


Damos un programa que computa g.
Damos un programa que computa g.
Línea 33: Línea 33:
Demostrar que si f es además biyectiva, f^-1 es computable.  
Demostrar que si f es además biyectiva, f^-1 es computable.  


==== Solución ====
'''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.
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.
Línea 41: Línea 41:
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.
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 ===
'''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.
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.
Línea 58: Línea 58:
         0 en otro caso
         0 en otro caso


=== Solución ===
'''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.
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.
Línea 186: Línea 186:


Definir un predicado pr P tal que <math>A = {x : (\forall y)P(x,y)}</math> no sea re.
Definir un predicado pr P tal que <math>A = {x : (\forall y)P(x,y)}</math> no sea re.
Sea <math>P(x,y) := STP(x,x,y)=0</math>
Como STP es p.r., <math>P(x,y)</math> es claramente p.r. también
Notemos ahora que <math>B=\{x: (\forall y) STP(x,x,y)=0\}</math> es lo mismo que
<math>B=\{x | \Phi_x (x)\uparrow\}</math>  , o sea, es el complemento del famoso conjunto <math>K</math> (x tal que Halt(x,x)), que ya sabíamos que no es r.e. porque lo probamos en la teórica/práctica.


== Ejercicio 20 ==
== Ejercicio 20 ==

Revisión del 17:37 18 feb 2007

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.

Sea Como STP es p.r., es claramente p.r. también Notemos ahora que es lo mismo que , o sea, es el complemento del famoso conjunto (x tal que Halt(x,x)), que ya sabíamos que no es r.e. porque lo probamos en la teórica/práctica.

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 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,

2.

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,

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 :)