Práctica 3 (LyC Verano)
Ejercicio 1
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: \mathbb{N} \rightarrow \mathbb{N}} computable.
Item A
Demostrar que 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 g(x) = \begin{cases} min_y\; f(y) = x & \textrm{si existe } y \textrm{ tal que } f(y) = x \\ \uparrow & \textrm{si no} \end{cases} }
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 programa 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, 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^{-1}} es computable.
Solució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^{-1}(x) = min_y\; f(y) = x}
Notar que el programa que dimos computa 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^{-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 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: \mathbb{N} \rightarrow \mathbb{N}} una función computable y sobreyectiva. Probar que existe una función computable e inyectiva 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: \mathbb{N} \rightarrow \mathbb{N}} 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 g(f(x)) \le x} para todo x perteneciente a 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 \mathbb{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 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^{-1}} . Si f es inyectiva y sobreyectiva (i.e. biyectiva) se puede definir una 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^{-1}} 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 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 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_i} 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 g(f(x_i)) = x} . Pero siempre habrá un único 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_1} 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 g(f(x_1)) = x} y además 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_1} es más chico que todos los 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_i} . Este 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_1} se encuentra con la minimizació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 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 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_1} 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 x_2} distintos no pueden provenir del mismo y, dado que esto violaría la definición de función.
Ejercicio 3
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: \mathbb{N} \rightarrow \mathbb{N}} una función computable biyectiva. Probar que Halt(f(x), x) no es computable. Sugerencia: considerar 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 h(x) = \begin{cases} 1 & \textrm{si\ } \neg\textrm{HALT}(x, f^-1(x)) \\ \uparrow & \textrm{si no} \end{cases} }
Solucion
El siguiente programa computa h, suponiendo que HALT(f(x),x) sea computable:
[A] IF HALT(f(f^-1(x)), f^-1(x)) GOTO A Y <- 1
que es equivalente a:
[A] IF HALT(x, f^-1(x)) GOTO A Y <- 1
Llamemos P a este programa, entonces existe e tal que #(P) = e
Ahora bien, por la definición de HALT:
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(f(e), e) \Longleftrightarrow h(f(e)) \downarrow}
Y por la definición de h:
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 h(f(e))\downarrow \;\Longleftrightarrow \neg HALT(f(e), e)}
Lo que nos lleva a un absurdo, que proviene de la única suposición que hicimos, que es que HALT(f(x), x) es computable.
Ejercicio 4
Sean f, g y h las funciones dadas por:
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) = \begin{cases} \Phi(x,x) + 1 & si\; \Phi(x,x)\downarrow \\ \uparrow & sino \end{cases} }
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) = \begin{cases} 1 & \textrm{si\ } x \in Dom(f) \\ \uparrow & sino \end{cases} }
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 h(x) = \begin{cases} 0 & \textrm{si\ } \Phi(x,x)\downarrow \\ \uparrow & sino \end{cases} }
Probar que son parcialmente computables.
Solucion
Para resolver esto es suficiente con dar 3 programas que computen cada una de estas funciones.
Este programa computa f:
Y <- fi(x,x) + 1
Este programa computa g:
Z <- f(x) Y <- 1
Y este computa h:
Y <- not(g(x))
Ejercicio 5
Probar que la siguiente función es primitiva recursiva:
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) = \begin{cases} 1 & \textrm{si\ } x = \langle\langle a,b\rangle ,c\rangle \; y\; \Phi(b,a) \textrm{\ termina\ en\ menos\ de\ c\ pasos} \\ 0 & sino \end{cases} }
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 "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(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 computable 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.
Solucion
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(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 f} 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 g} computable la función que la extiende. Podríamos reescribir la función 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 g} de la siguiente manera:
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, g(x_1,\dots,x_n,y))}
Lo cual es absurdo, ya que HALT no es computable y con esta definición es claramente computable.
La idea es que como f te devuelve el número de pasos necesarios para terminar la ejecución de y termina, no importa qué te devuelva la extensión g ya que podés chequear si es efectivamente el número de pasos o si es uno de los casos en que f se colgaba y g llenó el agujero.
Ejercicio 7
Probar que existen funciones g y h primitivas recursivas 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 g: \mathbb{N}^3 \rightarrow \mathbb{N}, \Phi_z(u,v,w) = \Phi_{g(u,v,w)}(z)}
- 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 h: \mathbb{N} \rightarrow \mathbb{N}, \Phi_{h(n,m)}(x) = \Phi_n(x) + \Phi_m(x)}
Solucion Item 1
Definimos una 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 \xi(z, u, v, w) = \Phi_z(u,v,w)\,\!}
Esta función es parcialmente computable por lo tanto existe un programa que la computa y un número e asociado a tal programa. Ahora sabemos que se cumple la igualdad
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(z, u,v,w) = \Phi_z(u,v,w)\,\!}
Usando el teorema del parámetro sabemos que existe una función f 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_{f(e, u, v, w)}(z) = \Phi_e(z, u,v,w) = \Phi_z(u,v,w)\,\!}
La función f es PR ya que es la que nos dá el Teorema del Parámetro. Esta función toma 4 parámetros pero como nosotros ya conocemos el e del programa anterior podemos definir la función g
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(u,v,w) = f(e,u,v,w)\,\!}
Y así nos queda una función g primitiva recursiva con la aridad necesaria que cumple
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_{f(e, u, v, w)}(z) = \Phi_{g(u,v,w)}(z) = \Phi_z(u,v,w)\,\!}
Solucion Item 2
De la misma manera que en el punto anterior definimos 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 \xi(x, n, m) = \Phi_n(x) + \Phi_m(x)\,\!}
Y como es parcialmente computable sabemos que existe un programa P con número e que la computa. 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 \Phi_e(x, n, m) = \Phi_n(x) + \Phi_m(x)\,\!}
Usando el Teorema del Parámetro existe una función f primitiva recursiva 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_{f(e,n,m)}(x) = \Phi_e(x, n, m) = \Phi_n(x) + \Phi_m(x)\,\!}
Definimos 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 h(n,m) = f(e,n,m)\,\!}
que cumple con lo pedido.
Ejercicio 8
Probar que las siguientes funciones no son computables
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_1(x) = \begin{cases} 1 & si\ \Phi_x(x) \neq x \\ 0 & \textrm{sino} \end{cases} }
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_2(x,y) = \begin{cases} 1 & si\ y \in \textrm{ran}\ \Phi_x \\ 0 & \textrm{sino} \end{cases} }
Solución del primer caso
Definimos una 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 g(x,y) = \begin{cases} x & si\ f_1(x) \\ x + 1 & \textrm{sino} \end{cases} }
Por el teorema de la recursión sabemos que existe un e 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_e(y) = g(e,y) = \begin{cases} e & si\ f_1(e) \\ e + 1 & \textrm{sino} \end{cases} }
Como la igualdad debe valer para todo y' podemos fijar y = e. Entonces podemos deducir que hay dos casos
1. 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 e \Longleftrightarrow g(e, e) \neq e \Longleftrightarrow \neg f_1(e) \Longleftrightarrow \Phi_e(e) = e} . Absurdo!
2. 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) = e \Longleftrightarrow g(e, e) = e \Longleftrightarrow f_1(e) \Longleftrightarrow \Phi_e(e) \neq e} . Absurdo!
La función no puede ser computable.
Solución del segundo caso
Si fuera computable podemos escribir a HALT(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 f_2} (x,y). No puede ser computable.
Ejercicio 9
Probar usando el teorema de la recursion que la siguiente funcion no es computable
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, y) = \begin{cases} 1\ si \ \Phi_x (y) > x \\ 0 \ sino \end{cases}}
Sugerencia: considerar la funcion
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, y) = \begin{cases} x\ si \ f(x,y) = 1 \\ x + 1 \ sino \end{cases}}
Solucion
Supongo f computable, entonces g tambien lo es. Por el teorema de la recursion se que existe e 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_e(y) = g(e,y)\,\!} , pero 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 g(e, y) = \begin{cases} e\ si \ f(e,y) = 1\\ e + 1 \ sino \end{cases}}
donde 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(e,y) = 1 \Rightarrow \Phi_e(y) > e}
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_e(y) = g(e,y) = e \Rightarrow \Phi_e(y) > e.}
Absurdo
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_e(y) = e+1 \Rightarrow \Phi_e(y) \leq e.}
Absurdo
El absurdo viene de suponer f computable.
Ejercicio 10
Probar que las siguientes funciones no son computables
Item A
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) = \begin{cases} 1 & si\ \Phi _x(x) = 2x \\ 0 & \textrm{sino} \end{cases} }
Supongo f es computable, por ende es total
Sea g(x,y) 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 g(x,y) = \begin{cases} 2x+1 & si f(x) \\ 2x & \textrm{sino} \end{cases} }
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
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) = \begin{cases} 1 & si\ dom(\Phi _x) = \emptyset \\ 0 & \textrm{sino} \end{cases} }
Supongo f es computable
Sea g(x,y) 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 g(x,y) = \begin{cases} 1 & si\ f(x) \\ \uparrow & \textrm{sino} \end{cases} }
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
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,y) = \begin{cases} 1 & si\ \Phi _x = \Phi _y \\ 0 & \textrm{sino} \end{cases} }
Supongo f es computable, por ende tambien total
Sea g(x,y) 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 g(x,y) = \begin{cases} \Phi _y + 1 & si\ f(x,y) \\ \Phi _y & \textrm{sino} \end{cases} }
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
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) = \begin{cases} 1 & si\ Im(\Phi _x)\ \textrm{es\ infinita} \\ 0 & \textrm{sino} \end{cases} }
Supongo f es computable, por ende tambien es total
Sea g(x,y) 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 g(x,y) = \begin{cases} 0 & si\ f(x) \\ y & \textrm{sino} \end{cases} }
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)} finita, 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) = \mathbb{N}}
Item E
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) = \begin{cases} 1 & si\ 1 \in dom(\Phi _x) \\ 0 & \textrm{sino} \end{cases} }
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 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,y) = \begin{cases} \uparrow & si\ f(x) \\ 0 & \textrm{sino} \end{cases} }
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 11
Probar que la siguiente función es parcialmente computable:
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_2(x,y) = \begin{cases} 1 & si\ y \in \textrm{ran}\ \Phi_x \\ \uparrow & \textrm{sino} \end{cases} }
(comparar con la funcion f2 del Ejercicio 8)
Solución
La función es computada por el programa
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(y)}
Y <- 1
Ejercicio 12
Analizar la validez de las siguientes afirmaciones
Item A
Si B es r.e., entonces B es computable o su complemento es computable.
Solucion
Falso.
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)\downarrow \} }
B es r.e., pero no es computable, ni tampoco su complemento. Si lo fueran, entonces el Halting problem seria computable.
Item B
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 B_1,...,B_k} son r.e., entonces la union tambien lo es.
Solucion
Verdadero.
Basta construir un programa que vaya evaluando en paralelo todas las posibilidades, hasta que alguno termine.
Item C
Idem anterior, pero si la cantidad de conjuntos es infinita.
Solucion
Falso.
Si la proposición fuera verdadera, entonces cualquier conjunto de naturales sería r.e.:
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 A} un conjunto de naturales cualquiera. Definimos la familia de conjuntos 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_i = \{ x: x\in A\land x < i \}} . Los 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_i} son todos finitos, por lo tanto son todos computables, por lo tanto son todos r.e. Además, es claro 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 = \cup_{i=1}^\infty B_i} . Por lo tanto, si la proposición fuera verdadera, 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} tendría que ser r.e.
Pero sabemos que existen conjuntos de naturales que no son r.e. (por ejemplo el complemento 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 K} ). Por lo tanto, la proposición debe ser falsa.
Ejercicio 13
Sea B un conjunto infinito
Item A
Probar que B es c.e. sii existe una funcion f inyectiva computable tal que la imagen de f sea B.
Solucion
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} )
Como B es c.e., existe una funcion g primitiva recursiva (por lo tanto, computable) tal que su imagen sea B. Defino f en funcion de g:
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(0) = g(0)}
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(n+1) = g(min_t((\forall i \leq n) g(t) \neq f(i))}
Intuitivamente, f va seleccionando todos los valores de g tal que no se hayan repetido anteriormente. Como B es infinito, siempre existira algun nuevo valor t que no sea repetido. Por lo tanto, la minimizacion es propia y f resulta computable e inyectiva, pues no repite valores; y su imagen es igual a B.
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 \Leftarrow} )
Existe una funcion f inyectiva computable tal que su imagen es igual a B, por lo tanto, B es r.e.
Se puede usar la funcion del 1.a para probarlo.
Item B
Probar que B es computable sii existe una funcion f de una variable computable y creciente tal que Im f = B.
Solucion
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} )
B = {x : B(x)} = {f(0), f(1), ... }
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(0) = min_t (B(t))}
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(n+1) = min_t (f(n) < t \wedge B(t))}
La idea de f es que va probando con todos los numeros naturales y para cada uno de ellos chequea si B(i) es verdadero o no. Si lo es, entonces lo devuelve como valor de la funcion, si no, sigue probando.
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 \Leftarrow} )
B es computable sii su funcion caracteristica B(x) lo es.
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) = (\exists t \leq x) f(t) = x}
Como f es computable, entonces B lo es.
Ejercicio 14
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) = f(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 15
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.
Solución
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 16
Ejercicio 17
=>) Sea A = We = {x: Φx↓} => x є A si existe un tiempo t tal que Φe(x)↓, entonces
A = {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 \exists}
t) STP(1)(x,e,t)}, y se sabe que STP es un predicado PR
<=) Sea el predicado PR J(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 \exists}
y) P(x,y), y el siguiente programa P:
[A] IF J(Z)=1 GOTO F
Z++
GOTO A
[F] Y <- 1
Como puede verse, P computa la funcion parcialmente computable
f(x) = {1 si J(x)=1
{↑ sino
Con lo cual B = dom f => B es RE
Ejercicio 18
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 19
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 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 N - B} 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 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 \ : \ \Phi_x \ es\ una\ funcion\ parcial\}} 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:
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,y) = \begin{cases} 1\ si\ x \in A \\ \uparrow\ sino \end{cases}} Por el teorema de la recursión, existe un e 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_e(y) = f(e,y)} , pero entonces:
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 e \in A \rightarrow \Phi_e(y)=1 \rightarrow e\ es\ total} (Absurdo porque partimos de que e era parcial y por eso estaba en A)
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 e \notin A \rightarrow \Phi_e(y)\uparrow \rightarrow e\ es\ parcial} (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
Probar que existe un 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 e} 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 W_e=\{e\}} . Tal e existe,por definición 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 W_e} , si y sólo si existe un 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 e} 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 \{e\}=\{x \in N\ |\ \Phi_e(x)\downarrow\}} .
Solucion
Definimos
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,y) = \begin{cases} 1\ si\ y = x \\ \uparrow\ sino \end{cases}}
Por el teorema de la recursión, existe un e 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_e(y) = f(e,y)} , pero 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 \Phi_e(y)} estará definida solo si y=e, es decir, el dominio 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 \Phi_e(y)} será e, eso significa 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 W_e=\{e\}} que era lo que queriamos probar.
Ejercicio 21
Demostrar que las funciones definidas en el Ejercicio 10 no son computables aplicando el Teorema de Rice
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
A = {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 \Phi _x = \Phi _0} }
Quiero ver que A no es computable por Rice. Para esto tengo que probar que:
1. 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 \neq \emptyset}
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, 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 \neq \emptyset}
2. 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 \neq 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, 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 \neq 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 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 _0} (la función nula). Entonces dado x perteneciente a A 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 _x = \Phi _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 :)
