Edición de «Práctica 8: Funciones Primitivas Recursivas (Lógica y Computabilidad)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 1: | Línea 1: | ||
==Ejercicio 01== | ==Ejercicio 01== | ||
*1. Esta definicion no es por recursion primitiva: la llamada recursiva DEBE ser con x e y. | *1. Esta definicion no es por recursion primitiva: la llamada recursiva DEBE ser con x e y. | ||
Línea 6: | Línea 4: | ||
*3. Si tomamos h(x) = φ(0, x) y g(x1, x2, x3) = φ(x2, s(x1)), se ve que ambas son totales. Ahora, podemos reescribir f(x, 0) = h(x) y f(x, y+1) = g(y, f(x, y), x), con lo cual, nos habian dado una definicion por recursion primitiva. | *3. Si tomamos h(x) = φ(0, x) y g(x1, x2, x3) = φ(x2, s(x1)), se ve que ambas son totales. Ahora, podemos reescribir f(x, 0) = h(x) y f(x, y+1) = g(y, f(x, y), x), con lo cual, nos habian dado una definicion por recursion primitiva. | ||
<pre> | |||
*a) No es recursiva primitiva. Me falta decir porqué, pero parece que el termino ''y + 1'' no se achica en cada paso recursivo | *a) No es recursiva primitiva. Me falta decir porqué, pero parece que el termino ''y + 1'' no se achica en cada paso recursivo | ||
*b) Si. Sea h(x) = ψ(x) y <math>g(x,y,z) = z + \varphi</math>. | *b) Si. Sea h(x) = ψ(x) y <math>g(x,y,z) = z + \varphi</math>. | ||
f(x,0) = h(x) | |||
f(x, y + 1) = g(x,y,f(x,y)) | |||
*c) Si. Sea <math>h(x) = \varphi(0,x)</math> y <math>g(x,y,z) = \varphi(z, y + 1)</math>. | *c) Si. Sea <math>h(x) = \varphi(0,x)</math> y <math>g(x,y,z) = \varphi(z, y + 1)</math>. | ||
f(x,0) = h(x) | |||
f(x, y + 1) = g(x,y,f(x,y)) | |||
</pre> | |||
==Ejercicio 02== | ==Ejercicio 02== | ||
Línea 156: | Línea 155: | ||
*7. Pr(x, y) = Σ {x<=i<=y} primo(i), donde primo es la f.p.r. que nos dice si un numero es primo. | *7. Pr(x, y) = Σ {x<=i<=y} primo(i), donde primo es la f.p.r. que nos dice si un numero es primo. | ||
*8. Basta definir G(x, y) = f11 (x, y), donde f11 se definio en el inciso 1 del ejercicio 4. | *8. Basta definir G(x, y) = f11 (x, y), donde f11 se definio en el inciso 1 del ejercicio 4. | ||