Práctica 3 (LyC Verano)

Ejercicio 1

Sea $f:\mathbb {N} \rightarrow \mathbb {N}$ computable.

Item A

Demostrar que la función

$g(x)={\begin{cases}min_{y}\;f(y)=x&{\textrm {siexiste}}y{\textrm {talque}}f(y)=x\\\uparrow &{\textrm {sino}}\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, $f^{-1}$ es computable.

Solución

$f^{-1}(x)=min_{y}\;f(y)=x$

Notar que el programa que dimos computa $f^{-1}$. Como f es biyectiva, es inyectiva. Esto asegura que el resultado de la expresión min {y:f(y) = x} devuelve no sólo el mínimo y, sino el único. Además, la sobreyectividad nos asegura la existencia de tal y, con lo cual el programa no puede colgarse.

Ejercicio 2

Sea $f:\mathbb {N} \rightarrow \mathbb {N}$ una función computable y sobreyectiva. Probar que existe una función computable e inyectiva $g:\mathbb {N} \rightarrow \mathbb {N}$ tal que $g(f(x))\leq x$ para todo x perteneciente a $\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 $f^{-1}$. Si f es inyectiva y sobreyectiva (i.e. biyectiva) se puede definir una $f^{-1}$ tal que $f^{-1}(x)=g(f(x))=x$, para todo x natural.

Si debilitamos la hipótesis sobre f, y sólo pedimos que sea sobreyectiva, pasa a haber más de un $x_{i}$ tal que $g(f(x_{i}))=x$. Pero siempre habrá un único $x_{1}$ tal que $g(f(x_{1}))=x$ y además $x_{1}$ es más chico que todos los $x_{i}$. Este $x_{1}$ se encuentra con la minimización:

$min_{y}\;f(y)=x$

Por otra parte, esta minimización es computable, dado que está garantizado por la sobreyectividad de f la existencia de al menos un y que verifique f(y) = x. Nuevamente, esta función se computa con el programa del ejercicio 1, item A. Por último, g es inyectiva porque en la expresión f(y) = x, dos valores $x_{1}$ y $x_{2}$ distintos no pueden provenir del mismo y, dado que esto violaría la definición de función.

Ejercicio 3

Sea $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:

$h(x)={\begin{cases}1&{\textrm {si\ }}\neg {\textrm {HALT}}(x,f^{-}1(x))\\\uparrow &{\textrm {sino}}\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:

$HALT(f(e),e)\Longleftrightarrow h(f(e))\downarrow$

Y por la definición de h:

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

$f(x)={\begin{cases}\Phi (x,x)+1&si\;\Phi (x,x)\downarrow \\\uparrow &sino\end{cases}}$

$g(x)={\begin{cases}1&{\textrm {si\ }}x\in Dom(f)\\\uparrow &sino\end{cases}}$

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

$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 "$\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 $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 $f$ es extensible y sea $g$ computable la función que la extiende. Podríamos reescribir la función HALT con $g$ de la siguiente manera:

$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. $g:\mathbb {N} ^{3}\rightarrow \mathbb {N} ,\Phi _{z}(u,v,w)=\Phi _{g(u,v,w)}(z)$
2. $h:\mathbb {N} \rightarrow \mathbb {N} ,\Phi _{h(n,m)}(x)=\Phi _{n}(x)+\Phi _{m}(x)$

Solucion Item 1

Definimos una función $\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

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

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

$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

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

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

$\Phi _{f(e,n,m)}(x)=\Phi _{e}(x,n,m)=\Phi _{n}(x)+\Phi _{m}(x)\,\!$

Definimos la función

$h(n,m)=f(e,n,m)\,\!$

que cumple con lo pedido.

Ejercicio 8

Probar que las siguientes funciones no son computables

$f_{1}(x)={\begin{cases}1&si\ \Phi _{x}(x)\neq x\\0&{\textrm {sino}}\end{cases}}$

$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

$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

$\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. $\Phi _{e}(e)\neq e\Longleftrightarrow g(e,e)\neq e\Longleftrightarrow \neg f_{1}(e)\Longleftrightarrow \Phi _{e}(e)=e$. Absurdo!

2. $\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) = $f_{2}$(x,y). No puede ser computable.

Ejercicio 9

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

$f(x,y)={\begin{cases}1\ si\ \Phi _{x}(y)>x\\0\ sino\end{cases}}$

Sugerencia: considerar la funcion

$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 $\Phi _{e}(y)=g(e,y)\,\!$, pero entonces:

$g(e,y)={\begin{cases}e\ si\ f(e,y)=1\\e+1\ sino\end{cases}}$

donde $f(e,y)=1\Rightarrow \Phi _{e}(y)>e$

Si $\Phi _{e}(y)=g(e,y)=e\Rightarrow \Phi _{e}(y)>e.$ Absurdo
Si $\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

$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 $g(x,y)={\begin{cases}2x+1&sif(x)\\2x&{\textrm {sino}}\end{cases}}$

Por teorema de la recursion, $\exists e/\Phi _{e}(y)=g(e,y)$

Supongo $\Phi _{e}(e)=2e$ $\Rightarrow f(e)\Rightarrow g(e,e)=\Phi _{e}(e)=2e+1\neq 2e$

Supongo $\Phi _{e}(e)\neq 2e$ $\Rightarrow \alpha (f(e))\Rightarrow g(e,e)=\Phi _{e}(e)=2e$

Absurdo que proviene de suponer que f es computable

Todos los items siguientes se resuelven con el mismo mecanismo

Item B

$f(x)={\begin{cases}1&si\ dom(\Phi _{x})=\emptyset \\0&{\textrm {sino}}\end{cases}}$

Supongo f es computable

Sea g(x,y) tal que $g(x,y)={\begin{cases}1&si\ f(x)\\\uparrow &{\textrm {sino}}\end{cases}}$

Por teorema de la recursion, $\exists e/\Phi _{e}=g(e)$

Evaluando g en e se llega al absurdo

Item C

$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 $g(x,y)={\begin{cases}\Phi _{y}+1&si\ f(x,y)\\\Phi _{y}&{\textrm {sino}}\end{cases}}$

Por teorema de la recursion, $\exists e/\Phi _{e}(y)=g(e,y)$

Sea a tal que $\Phi _{a}\downarrow$

Por teorema del parametro, $\exists s/\Phi _{s}=g(e,a)=\Phi _{e}(a)$

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

Item D

$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 $g(x,y)={\begin{cases}0&si\ f(x)\\y&{\textrm {sino}}\end{cases}}$

Por teorema de la recursion, $\exists e/\Phi _{e}(y)=g(e,y)$

Supongo $Im(\Phi _{e})$ infinita, $\Rightarrow f(e)\Rightarrow (\forall y)g(e,y)=\Phi _{e}(y)=0\Rightarrow Im(\Phi _{e})={0}$

Supongo $Im(\Phi _{e})$ finita, $\Rightarrow \alpha (f(e))\Rightarrow (\forall y)g(e,y)=\Phi _{e}(y)=y\Rightarrow Im(\Phi _{e})=\mathbb {N}$

Item E

$f(x)={\begin{cases}1&si\ 1\in dom(\Phi _{x})\\0&{\textrm {sino}}\end{cases}}$

La condicion equivale a decir que $\Phi _{x}(1)\downarrow$

Supongo f es computable, por ende tambien es total

Sea g(x,y) tal que $g(x,y)={\begin{cases}\uparrow &si\ f(x)\\0&{\textrm {sino}}\end{cases}}$

Por teorema de la recursion, $\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:

$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

$\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.

$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 $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 $A$ un conjunto de naturales cualquiera. Definimos la familia de conjuntos $B_{i}=\{x:x\in A\land x<i\}$. Los $B_{i}$ son todos finitos, por lo tanto son todos computables, por lo tanto son todos r.e. Además, es claro que $A=\cup _{i=1}^{\infty }B_{i}$. Por lo tanto, si la proposición fuera verdadera, $A$ tendría que ser r.e.

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

$\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:

$f(0)=g(0)$
$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.

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

$\Rightarrow$)

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

$f(0)=min_{t}(B(t))$
$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.

$\Leftarrow$)

B es computable sii su funcion caracteristica B(x) lo es.
$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 $A=\{x:f(x)\in B\}$ es re.

Solución

Como B es re, existe g parcialmente computable tal que $B=\{x:g(x)\downarrow \}$

Para que A sea re, tiene que existir una funcion h parcialmente computable tal que $A=\{x:h(x)\downarrow \}$.

Sea h = g(f(x)), parcialmente computable por ser composicion de pc. $g(f(x))=f(x)\in B$

Entonces A es re.

Ejercicio 17

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

<=) Sea el predicado PR J(x) = ($\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 $A={x:(\forall y)P(x,y)}$ no sea re.

Sea $P(x,y):=STP(x,x,y)=0$ Como STP es p.r., $P(x,y)$ es claramente p.r. también Notemos ahora que $B=\{x:(\forall y)STP(x,x,y)=0\}$ es lo mismo que $B=\{x|\Phi _{x}(x)\uparrow \}$ , o sea, es el complemento del famoso conjunto $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 $B=\{x\ :\ \Phi _{x}\ es\ una\ funcion\ total\}$

a. Probar que B no es r.e.

b. Probar que $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 $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:

$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: $\Phi _{e}(y)=f(e,y)$, pero entonces:

Si $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 $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 $e$ tal que $W_{e}=\{e\}$. Tal e existe,por definición de $W_{e}$, si y sólo si existe un $e$ tal que $\{e\}=\{x\in N\ |\ \Phi _{e}(x)\downarrow \}$.

Solucion

Definimos

$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: $\Phi _{e}(y)=f(e,y)$, pero entonces:

$\Phi _{e}(y)$ estará definida solo si y=e, es decir, el dominio de $\Phi _{e}(y)$ será e, eso significa que $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 $\Phi _{x}=\Phi _{y}$
         0  si no

A = {x: $\Phi _{x}=\Phi _{0}$}

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

1. $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, $A\neq \emptyset$

2. $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, $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 $\Phi _{0}$ (la función nula). Entonces dado x perteneciente a A y $\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 :)