Diferencia entre revisiones de «Práctica 9: Recursividad (Lógica y Computabilidad)»
De Cuba-Wiki
Sin resumen de edición |
Sin resumen de edición |
||
Línea 1: | Línea 1: | ||
== Ej. 12 == | |||
Pruebo que existe f(n,m) recursiva primitiva. | |||
Defino <math>g(x,n,m) = \phi(x,n) + \phi(x,m)</math> , g es claramente computable. Entonces existe z tal que <math>g(x,n,m) = \phi(x,n,m,z)</math>. | |||
Por el Teorema del Parametro, existe <math>S_2^1(n,m,z)</math> tal que <math>\phi(x,n,m,z) = \phi(x,S_2^1(n,m,z))</math>. | |||
Entonces <math>f(n,m) = S_2^1(n,m,z)</math> 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. | Dada f recursiva parcial, se dice extensible si existe una funcion g total tal que g en Dom(f) = f. | ||
Revisión del 05:32 1 dic 2006
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.
recursiva parcial
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
g(x) la extiende, entonces existe Y tal que = g
Absurdo!