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

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!