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

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.

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!