Práctica 3 (LyC Verano)
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.
¿Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(x) = \Phi _x(x)} ?
Sea Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle g(x_1, \dots, x_n, y) = \begin{cases} min_t STP(x_1,\dots,x_n,y,t)\ si \ \Phi_y (x_1,\dots,x_n) \downarrow \\ \uparrow \ sino \end{cases}}
Supongamos ahora Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle g} es extensible y sea Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f} computable la función que la extiende. Pero entonces, podríamos reescribir la función Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Halt} con Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f}
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Halt(x_1,\dots,x_n,y) = STP(x_1,\dots,x_n,y,f(x_1,\dots,x_n,y))} Lo cual es absurdo, ya que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Halt} no es computable y con esta definición es claramente computable. (la idea es que como Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle g} te devuelve en qué número de "iteración" Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle y} termina, no importa qué te devuelva la extensión Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f} ya que podés chequear si es fruta o es uno de los valores de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle g} , chequeando con Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle STP} si efectivamente Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle x} terminó en la cantidad de pasos que te dijo f)
Ejercicio 10
Probar que las siguientes funciones no son computables
Item A
f(x) = 1 si Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Phi _x(x) = 2x}
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, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \exists e / \Phi _e(y) = g(e,y)}
Supongo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Phi _e(e) = 2e} Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Rightarrow f(e) \Rightarrow g(e,e) = \Phi _e(e) = 2e+1 \neq 2e}
Supongo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Phi _e(e) \neq 2e} Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Rightarrow \alpha(f(e)) \Rightarrow g(e,e) = \Phi _e(e) = 2e}
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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle dom(\Phi _x) = \emptyset}
0 si no
Supongo f es computable
Sea g(x,y) tal que
g(x,y) = 1 si f(x)
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \uparrow}
si no
Por teorema de la recursion, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \exists e / \Phi _e = g(e)}
Evaluando g en e se llega al absurdo
Item C
f(x,y) = 1 si Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Phi _x = \Phi _y}
0 si no
Supongo f es computable, por ende tambien total
Sea g(x,y) tal que
g(x,y) = Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Phi _y + 1}
si f(x,y)
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Phi _y}
si no
Por teorema de la recursion, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \exists e / \Phi _e(y) = g(e,y)}
Sea a tal que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Phi _a\downarrow}
Por teorema del parametro, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \exists s / \Phi _s = g(e,a) = \Phi _e(a)}
Evaluando g en (s,a) se llega al absurdo
Item D
f(x) = 1 si Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Im(\Phi _x)}
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, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \exists e / \Phi _e(y) = g(e,y)}
Supongo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Im(\Phi _e) infinita} , Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Rightarrow f(e) \Rightarrow (\forall y) g(e,y) = \Phi _e(y) = 0 \Rightarrow Im(\Phi _e) = {0}}
Supongo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Im(\Phi _e) no infinita} , Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Rightarrow \alpha(f(e)) \Rightarrow (\forall y) g(e,y) = \Phi _e(y) = y \Rightarrow Im(\Phi _e) = Naturales}
Item E
f(x) = 1 si Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 1 \in dom(\Phi _x)}
0 si no
La condicion equivale a decir que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Phi _x(1)\downarrow}
Supongo f es computable, por ende tambien es total
Sea g(x,y) tal que
g(x,y) = Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \uparrow}
si f(x)
0 si no
Por teorema de la recursion, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \exists e / \Phi _e(y) = g(e,y)}
Evaluando g en (e,y) para todo y, se llega al absurdo
Ejercicio 12
Ejercicio 13
Probar que todo conjunto re infinito contiene un subconjunto computable infinito.
Solucion
Sea f p.r. tal que la imagen de f sea igual al conjunto B (r.e. e infinito).
Defino la funcion g tal que:
g(0) = 0 g(n+1) = f(min(t) (f(t) > g(n)))
Intuitivamente, la funcion g selecciona los valores que estan en orden creciente en la imagen de f. Como B es infinito, para cualquier indice elegido siempre existira otro mayor tal que la funcion resulte creciente. Por lo tanto, la minimizacion es propia y la funcion g resulta computable ademas de creciente.
Como g es computable y creciente, entonces su imagen define un conjunto, contenido en B, que es computable e infinito (vale por ej 12).
Ejercicio 14
Probar que si B es re y f es una funcion parcialmente computable, entonces Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A = {x : f(x) \in B}} es re.
Como B es re, existe g parcialmente computable tal que
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle B = {x : g(x)\downarrow}}
Para que A sea re, tiene que existir una funcion h parcialmente computable tal que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A = {x : h(x)\downarrow}} .
Sea h = g(f(x)), parcialmente computable por ser composicion de pc. Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle g(f(x)) = f(x) \in B}
Entonces A es re.
Ejercicio 17
Definir un predicado pr P tal que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A = {x : (\forall y)P(x,y)}} no sea re.
Sea Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle P(x,y) := STP(x,x,y)=0} Como STP es p.r., Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle P(x,y)} es claramente p.r. también Notemos ahora que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle B=\{x: (\forall y) STP(x,x,y)=0\}} es lo mismo que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle B=\{x | \Phi_x (x)\uparrow\}} , o sea, es el complemento del famoso conjunto Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle K} (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 18
Sea Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle B=\{ x \ : \ \Phi_x \ es\ una\ funcion\ total\}}
a. Probar que B no es r.e.
b. Probar que no es r.e.
Item a)
Este lo hicimos en clase.
Item b)
Lo que nos piden probar es que el complemento de B no es r.e. O sea, que el conjunto no es r.e. Supongamos entonces lo contrario. Esta suposición implica que la pertenencia a B es parcialmente computable (devuelve 1 si es true, se cuelga sino).
Definamos entonces:
Por el teorema de la recursión, existe un e tal que: , pero entonces:
Si (Absurdo porque partimos de que e era parcial y por eso estaba en A)
Si (Absurdo porque partimos de que e era total y por eso no estaba en A).
Pero entonces superabsurdo, que partió de suponer que A era un conjunto r.e.
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 :)
