Práctica 3 (LyC Verano)

De Cuba-Wiki

Plantilla:Back

Ejercicio 1[editar]

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[editar]

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[editar]

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[editar]

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[editar]

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[editar]

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[editar]

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[editar]

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[editar]

Probar que existen funciones g y h primitivas recursivas tal 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 g: \mathbb{N}^3 \rightarrow \mathbb{N}, \Phi_z(u,v,w) = \Phi_{g(u,v,w)}(z)}
  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 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[editar]

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

Como la igualdad debe valer para todo y' podemos fijar y = e. Entonces podemos deducir que hay dos casos

1. . Absurdo!

2. . Absurdo!

La función no puede ser computable.


Solución del segundo caso

Si fuera computable podemos escribir a HALT(x,y) = (x,y). No puede ser computable.

Ejercicio 9[editar]

Probar usando el teorema de la recursion que la siguiente funcion no es computable

Sugerencia: considerar la funcion


Solucion

Supongo f computable, entonces g tambien lo es. Por el teorema de la recursion se que existe e tal que , 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[editar]

Probar que las siguientes funciones no son computables

Item A[editar]

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[editar]

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[editar]

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[editar]

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[editar]

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[editar]

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[editar]

Analizar la validez de las siguientes afirmaciones

Item A[editar]

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[editar]

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[editar]

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[editar]

Sea B un conjunto infinito

Item A[editar]

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.

)


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[editar]

Probar que B es computable sii existe una funcion f de una variable computable y creciente tal que Im f = B.

Solucion

)

B = {x : B(x)} = {f(0), f(1), ... }


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.

)

B es computable sii su funcion caracteristica B(x) lo es.

Como f es computable, entonces B lo es.

Ejercicio 14[editar]

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[editar]

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

Solución

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 16[editar]

Ejercicio 17[editar]


=>) Sea A = We = {x: Φx↓} => x є A si existe un tiempo t tal que Φe(x)↓, entonces
A = {x: ( t) STP(1)(x,e,t)}, y se sabe que STP es un predicado PR


<=) Sea el predicado PR J(x) = ( 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[editar]

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 19[editar]

Sea

a. Probar que B no es r.e.

b. Probar que no es r.e.

Item A[editar]

Este lo hicimos en clase.

Item B[editar]

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[editar]

Probar que existe un tal que . Tal e existe,por definición de , si y sólo si existe un tal que .

Solucion

Definimos

Por el teorema de la recursión, existe un e tal que: , pero entonces:

estará definida solo si y=e, es decir, el dominio de será e, eso significa que que era lo que queriamos probar.

Ejercicio 21[editar]

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

Item C[editar]

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