Práctica 9: Recursividad (Lógica y Computabilidad)

Ejercicio 01

Como f es computable, tenemos un programa P tal que P = f. Dado n, vamos calculando f(0), f(1), y as´ı siguiendo con el STP. En alg´un momento, f(i) = n, porque la funci´on es total y biyectiva. Devolvemos ese valor. Es f´acil armar un programa que haga esto.

Ejercicio 02

Supongamos que f(x) es recursiva. Entonces, Gff (x, y) resulta trivialmente recursiva: basta calcular f(x) y ver si es y. Supongamos ahora que Gff (x, y) es recursiva. Como es la funci´on caracter´ıstica del gr´afico de una funci´on, 8x9!y Grf (x, y) = 1, pues todo punto debe tener una, y solo una, imagen. Entonces, corremos Grf (x, i), aumentando el i, hasta llegar al que nos da 1.

Ejercicio 03

Podemos definir g(x) = m´ınz(f(z) = x). Esta funci´on est´a bien definida, porque f es suryectiva. Entonces, siempre hay alg´un z que cumple f(z) = x para cualquier x. Adem´as de estar bien definida, es el resultado de aplicar minimizaci´on propia a una funci´on parcialmente computable y total. Entonces, es parcialmente computable y total. Los conjuntos {z|f(z) = x} y {z|f(z) = y} son disjuntos para y 6= x. Entonces, g(x) 6= g(y) para x 6= y, por lo que es inyectiva. Si evaluamos g(f(x)) = m´ınz(f(z) = f(x)). Como x cumple esto, el m´ınimo va a ser menor o igual que x, y g cumple todo lo pedido.

Ejercicio 04

Supongamos que HALT(X,X) es computable. Con ´el, construimos el programa P [A] IF HALT(X,X) GOTO A
P para con input X sii ¬HALT(X,X). Sea y0 = #(P). Entonces, HALT(y0, y0) , y0 para con input y0 , ¬HALT(y0, y0), lo cual nos da un absurdo.

Ejercicio 05

Supongamos que HALT(f(x), x) sea parcialmente computable. Entonces, tenemos un programa que lo computa. Sabemos que f es biyectiva y computable. Entonces, por el ejercicio 1, sabemos que f−1 tambi´en es computable. Luego, el siguiente programa computa HALT(x, f−1(x)).
Z f−1(X)
Y HALT(f(Z),Z) Entonces, el programa
[A] IF HALT(X, f−1(X)) GOTO A
Y 1 computa la h de la sugerencia. Sea h0 el n´umero de este programa. Observemos que h0 = f−1(f(h0)). Veamos qu´e pasa con h(f(h0)). Esto puede ser 1 o ". Si es 1, entonces �(f(h0), h0) ". Entonces h(f(h0)) ". Pero esto es una contradicci´on. Ahora, si es ", entonces �(f(h0), h0) #. Luego, h(f(h0)) #. Nuevmente tenemos una contradicci´on. Como lo ´unico que supusimos era que HALT(f(x), x) era parcialmente computable, esto es falso.

Ejercicio 06

Es computable. Vamos simulando los pasos de f(x). Si en alg´un momento para, entonces x pertenece al dominio de f y devolvemos un 1. Si nunca para, entonces, x no pertenec´ıa al dominio de f, y est´a bien que se cuelgue.

Ejercicio 07

Vamos simulando �(x, x), si para, devolvemos el resultado m´as 1. Si nunca para, entonces est´a bien que se cuelgue.

Ejercicio 08

Supongamos que f(x, y) es computable. Sea y0 un natural. Tenemos que �A(x) = f(x, y0) tambi´en tiene que ser computable. Pero �A es la funci´on caracter´ıstica del conjunto A = {x 2 N|y0 2 Im �x}, que tiene que ser recursivo. Entonces, tambi´en tiene que ser recursivo B = {�x|y 2 Im �x}. Pero la funci´on que devuelve constantemente y0 +1 no est´a en B, y la funci´on que devuelve constantemente y0 s´ı. Entonces, por el Teorema de Rice, B no es recursivo. Por ende tampoco lo son A, �A y f.

Ejercicio 12

Enunciado: Probar que existe una funcion primitiva recursiva f(n,m) tal que $\phi _{n}(x)+\phi _{m}(x)=\phi _{f(n,m)}(x)$.

Pruebo que existe f(n,m) recursiva primitiva.

Defino $g(x,n,m)=\phi (x,n)+\phi (x,m)$ , g es claramente computable. Entonces existe z tal que $g(x,n,m)=\phi (x,n,m,z)$.

Por el Teorema del Parametro, existe $S_{2}^{1}(n,m,z)$ tal que $\phi (x,n,m,z)=\phi (x,S_{2}^{1}(n,m,z))$.

Entonces $f(n,m)=S_{2}^{1}(n,m,z)$ es primitiva recursiva y cumple con lo pedido.

Ejercicio 13

• 1. Si miramos el conjunto {�x|Dom�x = ;}, por Rice no es recursivo. Luego, tampoco lo es el que nos dieron.

Ejercicio 14

• 1. La funci´on caracter´ıstica de este conjunto es f(x, y) = (1 si y 2 Im�x

0 si no
En el ejercicio 8 vimos que esta funci´on no es computable. Por lo tanto, el conjunto no es recursivo.

• 2. Si llamamos A al conjunto y suponemos que es recursivo, entonces

�A(x, y) = (1 si �x = �y 0 si no
tambi´en tiene que ser recursiva. Pero entonces, si y0 es tal que �y0 = 2, la funci´on constante 2., entonces �B = �A(x, y0) = (1 si �x = 2 0 si no
tambi´en tiene que ser recursiva. Pero esta es la funci´on caracter´ıstica del conjunto B = {x 2 N|�x = 2}. Si consideramos FB = {�x|�x = 2}, es f´acil ver que este conjunto no contiene a todas las funciones parcialmente computables. Entonces, por Rice, no es recursivo. Esto nos lleva a un absurdo, que dice que suponer que A era recursivo estuvo mal.

• 3. Consideramos F = {�x|Im�x es infinito}. Por Rice, este conjunto no es recursivo, luego tampoco lo es el original.

Ejercicio 15

• 1. Si f fuera recursiva, tendr´ıa que existir e tal que �e = f. Entonces �e(e) = (1 si �e(e) = 0 0 si �e(e) 6= 0

lo cual nos muestra que no puede existir un tal e. Luego, f no es computable.

• 2. Supongamos que f sea recursiva. Entonces, sea x0 tal que �x0 es la funci´on constante 0. Entonces, si f es recursiva, g(y) = f(x0, y) tambi´en lo es. Pero

g(y) = (1 si �y(y) 6= 0 0 si �y(y) = 0
Si esta funci´on fuera recursiva, tambi´en lo ser´ıa �(g). Pero esta es la funci´on del ejercicio anterior, que ya vimos que no es recursiva. Entonces, nuestra f tampoco lo era.

• 3. Si fuera computable, tambi´en lo ser´ıa g(x, y) = f(x, y, z0), donde z0 es tal que �z0 es la funci´on constante 0. Y por consecuencia, tambi´en lo ser´ıa g(x, x). Pero esta funci´on es la del inciso a, que vimos que no era computable. Entonces, nuestra f tampoco lo es.

Ejercicio 16

Para probar esto, primero probamos un resultado adicional. Si B = {f(n)|n 2 N}, con f una funci´on estrictamente creciente, parcialmente computable y total, entonces B es recursivo. Para verlo, basta ver que el siguiente programa
[A] IFf(Z) = X GOTO B
IFf(Z) > X GOTO E
Z Z + 1
GOTO A
[B] Y 1
GOTO E computa �B. Este programa termina siempre, as´ı que B es recursivo. Ahora, sea A r.e. e infinito. Tenemos una funci´on primitiva recursiva g(x) que nos va dando los elementos de A. Definimos f(0) = g(0), y suponiendo definida f(k) para todo k < n, definimos f(n) = g(m´ınz(g(z) > f(n − 1))). Esta minimizaci´on es propia, pues A es infinito. Entonces, siempre podemos encontrar un elemento de A mayor que todos los que tengamos. Esto nos da una f parcialmente computable, total, y estrictamente creciente. Si tomamos B = {f(n)|n 2 N}, tenemos que B es recursivo y que B � A.

Ejercicio 17

• 1. A [ B es r.e.: voy dando un elemento de A y uno de B. Para que sea m´as bonito, guardo los que di y no repito. A \ B tambi´en es r.e.: Voy guardando dos listas, la de elementos de A y la de elementos de B. Genero un n´umero de cada conjunto. Cada vez que genero, me fijo si est´a en la lista del otro. Si est´a, lo doy. Si no, por

el momento no.

• 2. Es falsa. Si tomamos B los programas que paran cuando se les da como entrada su n´umero de programa, y A todos los programas, entonces A\B son los programas que no se detienen cuando se les da su n´umero de programa como entrada. Si este conjunto fuera r.e., HALT(X,X) ser´ıa computable.
• 3. Es falso. Sea B = N, pensados como n´umeros de programas. Sea, A el conjunto de n´umeros de programasque computan la funci´on vac´ıa (la que no est´a definida en ning´un lado). En el ejercicio 20.c veremos que este subconjunto no es r.e.
• 4. Es falso. Ni HALT(X,X) es recursivo, ni su complemento, pero es r.e.
• 5. Es verdadero. Con un argumento diagonal, voy dando un elemento del primero, uno del segundo, otro del primero, otro del segundo, uno del tercero, etc.

Ejercicio 19

Para ver que B es r.e., vamos simulando todos los programas, y listamos los que van parando. Para ver que no es recursivo, usamos Rice con el conjunto {�x|�x(0) = 1}.

Ejercicio 20

• 1. Es r.e.: voy simulando �x(0) para todos los x, en orden. A medida que paran, los voy listando. Para ver que no es recursivo, aplico Rice al conjunto {�x|�x(0) #}
• 2. Es r.e.: idem el inciso anterior, pero con entrada x. No es recursivo, pues es HALT(x, x).
• 3. Aplicando Rice al conjunto {�x|Dom�x = ;} se ve que no es recursivo. Ahora, en forma an´aloga al inciso 1, se puede ver que Ak = {x 2 N|�x(k) #} es r.e. para todo k 2 N. Por el ejercicio 17, inciso 5, el conjunto S1k=0 Ak es r.e. Este conjunto es el complemento del que nos piden estudiar. Si el que nos piden fuera r.e., como su complemento tambi´en lo es, ser´ıa recursivo. Como no lo es, no es tampoco r.e.
• 4. El conjunto es completamente an´alogo al del inciso a, pero cambiando 0 por 1.

Ejercicio 21

Se deduce de combinar los teoremas 4.9 y 4.10 del libro de Davis

Ejercicio 22

En palabras, por el ejercicio anterior tenemos una f parcialmente computable y total que nos va dando los elementos de B. Entonces, armamos un programa que vaya enumerando esos elementos, pero que guarde los elementos que va dando como salidas. El siguiente programa nos da, entonces, esa tal funci´on modificada.
[A] Z2 f(Z)
IF Z2 NO ESTA EN LA LISTA Z3 GOTO B // Z3 guarda los elementos que doy como salida
Z Z + 1 // Si ya estaba en la lista,
GOTO A //genero otro elemento
[B] IF Lt(Z3) = X GOTO C // Si ya gener´e tantos elementos como me pidieron
AGREGO Z2 A LA LISTA Z3 // Si no, genero uno m´as
Z Z + 1
GOTO A
[C] Y Z2 Como este programa termina para todo X de entrada, tenemos que nuestro conjunto es la imagen de una funci´on parcialmente computable, total e inyectiva.

Porqueria

Dada f recursiva parcial, se dice extensible si existe una funcion g total tal que g en Dom(f) = f.

$\mathbf {f} (x)=\left\{{\begin{matrix}0&{\mbox{if}}\ x\in k,\\1&{\mbox{if}}\ x\notin k.\end{matrix}}\right.$

recursiva parcial

$\mathbf {f} (x)=\left\{{\begin{matrix}min_{t}STP(x,x,t)&{\mbox{if}}\ HALT(x,x),\\\uparrow &{\mbox{if}}\ \neg HALT(x,x).\end{matrix}}\right.$

Si existe g(x) que la extiende $\Rightarrow$ dado $x_{1}$ calculo $g(x).\phi _{x}^{1}(x)$

g(x) pasos

\phi (x,x) g(x)

todo esto creo, no sirve para nada

---

Ej practica 9

$\mathbf {(} x)=\left\{{\begin{matrix}\phi (x,x)+1&{\mbox{if}}\ \phi (x,x)\downarrow ,\\\uparrow &{\mbox{if}}\ not.\end{matrix}}\right.$

g(x) la extiende, entonces existe Y tal que $\phi (y)$ = g

$g(y)=\phi (y,y)+1=g(y)+1$

Absurdo!