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

Ej. 12

Enunciado: Probar que existe una funcion primitiva recursiva f(n,m) tal que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \phi_n(x) + \phi_m(X) = \phi_{f(n,m)}(x)} .

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

Defino Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle g(x,n,m) = \phi(x,n) + \phi(x,m)} , g es claramente computable. Entonces existe z tal que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle g(x,n,m) = \phi(x,n,m,z)} .

Por el Teorema del Parametro, existe Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle S_2^1(n,m,z)} tal que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \phi(x,n,m,z) = \phi(x,S_2^1(n,m,z))} .

Entonces Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 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.

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mathbf f (x) = \left\{\begin{matrix} 0 &\mbox{if}\ x \in k, \\ 1 &\mbox{if}\ x \notin k. \end{matrix}\right. }

recursiva parcial

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\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. }

Si existe g(x) que la extiende Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Rightarrow} dado Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle x_1} calculo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle g(x) . \phi_x^1(x)}

g(x) pasos

\phi (x,x) g(x)

todo esto creo, no sirve para nada

---

Ej practica 9

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \phi(y)} = g

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle g(y) = \phi(y,y) +1 = g(y) + 1}

Absurdo!