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 asi siguiendo con el STP. En algun momento, f(i) = n, porque la funcion es total y biyectiva. Devolvemos ese valor. Es facil armar un programa que haga esto.

Ejercicio 02

Supongamos que f(x) es recursiva. Entonces, Grf (x, y) resulta trivialmente recursiva: basta calcular f(x) y ver si es y. Supongamos ahora que Grf (x, y) es recursiva. Como es la funcion caracteristica del grafico de una funcion, ∀x∃!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) = minz(f(z) = x). Esta funcion esta bien definida, porque f es suryectiva. Entonces, siempre hay algun z que cumple f(z) = x para cualquier x. Ademas de estar bien definida, es el resultado de aplicar minimizacion propia a una funcion 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 != x. Entonces, g(x) != g(y) para x != y, por lo que es inyectiva. Si evaluamos g(f(x)) = minz(f(z) = f(x)). Como x cumple esto, el minimo 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 tambien 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 numero de este programa. Observemos que h0 = f^-1(f(h0)). Veamos que 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 contradiccion. Ahora, si es ↑, entonces ф(f(h0), h0) ↓. Luego, h(f(h0)) ↓. Nuevmente tenemos una contradiccion. 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 algun momento para, entonces x pertenece al dominio de f y devolvemos un 1. Si nunca para, entonces, x no pertenecia al dominio de f, y esta bien que se cuelgue.

Ejercicio 07

Vamos simulando ф(x, x), si para, devolvemos el resultado mas 1. Si nunca para, entonces esta bien que se cuelgue.

Ejercicio 08

Supongamos que f(x, y) es computable. Sea y0 un natural. Tenemos que XA(x) = f(x, y0) tambien tiene que ser computable. Pero XA es la funcion caracteristica del conjunto A = {x є N|y0 є Im фx}, que tiene que ser recursivo. Entonces, tambien tiene que ser recursivo B = {фx|y є Im фx}. Pero la funcion que devuelve constantemente y0 + 1 no esta en B, y la funcion que devuelve constantemente y0 si. Entonces, por el Teorema de Rice, B no es recursivo. Por ende tampoco lo son A, XA y f.

Ejercicio 09

Sea f(x) = ф(x, x)+1. Claramente, esta funcion es recursiva y no total. Supongamos que existe una g recursiva y total que coincide con f en todo el dominio de esta. Sea P un programa que computa a g, y y0 el numero de P. ф(y0, y0) ↓, pues g es total. Entonces y0 ε Dom(f). Entonces g(y0) = f(y0) = ф(y0, y0) + 1 = g(y0) + 1, lo cual nos da un absurdo.

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 funcion caracteristica de este conjunto es

f(x, y) = { 1 si y є Im фx
0 si no
En el ejercicio 8 vimos que esta funcion no es computable. Por lo tanto, el conjunto no es recursivo.

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

XA(x, y) = { 1 si фx = фy
0 si no
tambien tiene que ser recursiva. Pero entonces, si y0 es tal que фy0 = 2, la funcion constante 2., entonces
XB = XA(x, y0) = { 1 si фx = 2
0 si no
tambien tiene que ser recursiva. Pero esta es la funcion caracteristica del conjunto B = {x є N|фx = 2}. Si consideramos FB = {фx|фx = 2}, es facil 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, tendria que existir e tal que фe = f. Entonces

фe(e) = { 1 si фe(e) = 0
0 si фe(e) != 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 funcion constante 0. Entonces, si f es recursiva, g(y) = f(x0, y) tambien lo es. Pero

g(y) = { 1 si фy(y) != 0
0 si фy(y) = 0
Si esta funcion fuera recursiva, tambien lo seria α(g). Pero esta es la funcion del ejercicio anterior, que ya vimos que no es recursiva. Entonces, nuestra f tampoco lo era.

• 3. Si fuera computable, tambien lo seria g(x, y) = f(x, y, z0), donde z0 es tal que фz0 es la funcion constante 0. Y por consecuencia, tambien lo seria g(x, x). Pero esta funcion 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 є N}, con f una funcion estrictamente creciente, parcialmente computable y total, entonces B es recursivo. Para verlo, basta ver que el siguiente programa
[A] IF f(Z) = X GOTO B
IF f(Z) > X GOTO E
Z = Z + 1
GOTO A
[B] Y = 1
GOTO E
computa XB. Este programa termina siempre, asi que B es recursivo. Ahora, sea A r.e. e infinito. Tenemos una funcion 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(min z(g(z) > f(n-1))). Esta minimizacion 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 є N}, tenemos que B es recursivo y que B (= A.

Ejercicio 17

• 1. A U B es r.e.: voy dando un elemento de A y uno de B. Para que sea mas bonito, guardo los que di y no repito. A∩B tambien es r.e.: Voy guardando dos listas, la de elementos de A y la de elementos de B. Genero un numero de cada conjunto. Cada vez que genero, me fijo si esta en la lista del otro. Si esta, 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 numero de programa, y A todos los programas, entonces A\B son los programas que no se detienen cuando se les da su numero de programa como entrada. Si este conjunto fuera r.e., HALT(X,X) seria computable.
• 3. Es falso. Sea B = N, pensados como numeros de programas. Sea, A el conjunto de numeros de programasque computan la funcion vacia (la que no esta definida en ningun 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 18

Tengo un programa que me lista los elementos de B, y otro que computa f. Voy corriendo ambos. Esto es, hago un paso de f(0), y pido un elemento de B. Luego, el segundo de f(0) y el primero de f(1). Luego otro elemento de B, y sigo en f. Cada vez que f termina, guardo el par (x, f(x)) en una lista. Cada vez que doy un elemento de B, lo guardo en una lista. Cada vez que obtengo alguna cosa (f par´o, o tengo un elemento de B), barro la lista que corresponde, a ver si esta. Por ejemplo, cuando obtengo un elemento b de B, me fijo si en la lista de pares (x, f(x)) hay alguno tal que f(x) = b. Si es asi, devuelvo x. Si lo que obtuve fue un par, reviso la lista de elementos de B. Para evitar repetidos, guardo los x que voy dando como salida en otra lista. Si x es un elemento de la preimagen de B, quiere decir que en algun momento va a aparecer el par (x, f(x)) y en algun momento me va a aparecer f(x) en B. Entonces, en algun momento voy a devolver x.

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 analoga al inciso 1, se puede ver que Ak = {x ε N|фx(k) ↓} es r.e. para todo k ε N. Por el ejercicio 17, inciso 5, el conjunto U {k=0..inf} 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 tambien lo es, seria recursivo. Como no lo es, no es tampoco r.e.
• 4. El conjunto es completamente analogo 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 funcion 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 genere tantos elementos como me pidieron
AGREGO Z2 A LA LISTA Z3 // Si no, genero uno mas
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 funcion 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!