Diferencia entre revisiones de «Práctica 9: Recursividad (Lógica y Computabilidad)»
De Cuba-Wiki
(enunciado ej12) |
Sin resumen de edición |
||
Línea 1: | Línea 1: | ||
== | ==Ejercicio 01== | ||
==Ejercicio 02== | |||
==Ejercicio 03== | |||
==Ejercicio 04== | |||
==Ejercicio 05== | |||
==Ejercicio 06== | |||
==Ejercicio 07== | |||
==Ejercicio 08== | |||
==Ejercicio 09== | |||
==Ejercicio 10== | |||
==Ejercicio 11== | |||
==Ejercicio 12== | |||
Enunciado: Probar que existe una funcion primitiva recursiva f(n,m) tal que <math>\phi_n(x) + \phi_m(x) = \phi_{f(n,m)}(x)</math>. | Enunciado: Probar que existe una funcion primitiva recursiva f(n,m) tal que <math>\phi_n(x) + \phi_m(x) = \phi_{f(n,m)}(x)</math>. | ||
Línea 9: | Línea 20: | ||
Entonces <math>f(n,m) = S_2^1(n,m,z)</math> es primitiva recursiva y cumple con lo pedido. | Entonces <math>f(n,m) = S_2^1(n,m,z)</math> es primitiva recursiva y cumple con lo pedido. | ||
==Ejercicio 13== | |||
==Ejercicio 14== | |||
==Ejercicio 15== | |||
==Ejercicio 16== | |||
==Ejercicio 17== | |||
==Ejercicio 18== | |||
==Ejercicio 19== | |||
==Ejercicio 20== | |||
==Ejercicio 21== | |||
==Ejercicio 22== | |||
==Ejercicio 23== | |||
==Ejercicio 24== | |||
== Porqueria == | == Porqueria == | ||
Línea 21: | Línea 45: | ||
\end{matrix}\right. | \end{matrix}\right. | ||
</math> | </math> | ||
recursiva parcial | recursiva parcial | ||
Línea 36: | Línea 58: | ||
g(x) pasos | g(x) pasos | ||
\phi (x,x) g(x) | \phi (x,x) g(x) | ||
Línea 45: | Línea 65: | ||
---- | ---- | ||
Ej practica 9 | Ej practica 9 | ||
Línea 55: | Línea 74: | ||
\end{matrix}\right. | \end{matrix}\right. | ||
</math> | </math> | ||
g(x) la extiende, entonces existe Y tal que <math>\phi(y)</math> = g | g(x) la extiende, entonces existe Y tal que <math>\phi(y)</math> = g |
Revisión del 23:19 30 dic 2006
Ejercicio 01
Ejercicio 02
Ejercicio 03
Ejercicio 04
Ejercicio 05
Ejercicio 06
Ejercicio 07
Ejercicio 08
Ejercicio 09
Ejercicio 10
Ejercicio 11
Ejercicio 12
Enunciado: Probar que existe una funcion primitiva recursiva f(n,m) tal que .
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.
Ejercicio 13
Ejercicio 14
Ejercicio 15
Ejercicio 16
Ejercicio 17
Ejercicio 18
Ejercicio 19
Ejercicio 20
Ejercicio 21
Ejercicio 22
Ejercicio 23
Ejercicio 24
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!