Práctica 3 (LyC Verano)

De Cuba-Wiki
La versión para imprimir ya no se admite y puede contener errores de representación. Actualiza los marcadores del navegador y utiliza en su lugar la función de impresión predeterminada del navegador.

Plantilla:Back

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

  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

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

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:



donde

Si Absurdo
Si Absurdo

El absurdo viene de suponer f computable.

Ejercicio 10

Probar que las siguientes funciones no son computables

Item A

Supongo f es computable, por ende es total

Sea g(x,y) tal que

Por teorema de la recursion,

Supongo

Supongo

Absurdo que proviene de suponer que f es computable

Todos los items siguientes se resuelven con el mismo mecanismo

Item B

Supongo f es computable

Sea g(x,y) tal que

Por teorema de la recursion,

Evaluando g en e se llega al absurdo

Item C

Supongo f es computable, por ende tambien total

Sea g(x,y) tal que

Por teorema de la recursion,

Sea a tal que

Por teorema del parametro,

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

Item D

Supongo f es computable, por ende tambien es total

Sea g(x,y) tal que

Por teorema de la recursion,

Supongo infinita,

Supongo finita,

Item E

La condicion equivale a decir que

Supongo f es computable, por ende tambien es total

Sea g(x,y) tal que

Por teorema de la recursion,

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

Ejercicio 11

Probar que la siguiente función es parcialmente computable:

(comparar con la funcion f2 del Ejercicio 8)

Solución

La función es computada por el programa


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.


B es r.e., pero no es computable, ni tampoco su complemento. Si lo fueran, entonces el Halting problem seria computable.

Item B

Si 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 un conjunto de naturales cualquiera. Definimos la familia de conjuntos . Los son todos finitos, por lo tanto son todos computables, por lo tanto son todos r.e. Además, es claro que . Por lo tanto, si la proposición fuera verdadera, tendría que ser r.e.

Pero sabemos que existen conjuntos de naturales que no son r.e. (por ejemplo el complemento de ). 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

)

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:


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

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

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

Ejercicio 17


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

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

Sea

a. Probar que B no es r.e.

b. Probar que no es r.e.

Item A

Este lo hicimos en clase.

Item B

Lo que nos piden probar es que el complemento de B no es r.e. O sea, que el conjunto no es r.e. Supongamos entonces lo contrario. Esta suposición implica que la pertenencia a B es parcialmente computable (devuelve 1 si es true, se cuelga sino).

Definamos entonces:

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

Si (Absurdo porque partimos de que e era parcial y por eso estaba en A)

Si (Absurdo porque partimos de que e era total y por eso no estaba en A).

Pero entonces superabsurdo, que partió de suponer que A era un conjunto r.e.

Ejercicio 20

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

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

Item C

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

A = {x: }

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

1.

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

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

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

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

n(x) = 0

Entonces,

2.

Ejemplo: el programa que computa la función constante

g(x) = 8

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

Entonces,

3. A es un conjunto de índices

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

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

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

El resto sale de la misma forma :)