Ej. 12
Pruebo que existe f(n,m) recursiva primitiva.
Defino
, g es claramente computable. Entonces existe z tal que
.
Por el Teorema del Parametro, existe
tal que
.
Entonces
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.
![{\displaystyle \mathbf {f} (x)=\left\{{\begin{matrix}0&{\mbox{if}}\ x\in k,\\1&{\mbox{if}}\ x\notin k.\end{matrix}}\right.}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/c50c4b802d68cf6bde23ae2f84877db7678068ee)
recursiva parcial
![{\displaystyle \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.}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/9fa6848cdd2ba92c0540811fb131039ea8975ddf)
Si existe g(x) que la extiende
dado
calculo
g(x) pasos
\phi (x,x) g(x)
todo esto creo, no sirve para nada
Ej practica 9
![{\displaystyle \mathbf {(} x)=\left\{{\begin{matrix}\phi (x,x)+1&{\mbox{if}}\ \phi (x,x)\downarrow ,\\\uparrow &{\mbox{if}}\ not.\end{matrix}}\right.}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/466db81febf036b3b50723422b4f321f04b85740)
g(x) la extiende, entonces existe Y tal que
= g
Absurdo!