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. | ||
*2. Si tomamos h(x) = ψ(x) y | *2. Si tomamos h(x) = ψ(x) y g(x1, x2, x3) = u32 (x1, x2, x3) + φ(x3, 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. | *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 29: | Línea 28: | ||
*6. psq(x) = (sqrt(x) = x). | *6. psq(x) = (sqrt(x) = x). | ||
<pre> | |||
*a. Defino máximo recursivamente como: | *a. Defino máximo recursivamente como: | ||
max(x,0) = x | max(x,0) = x | ||
Línea 54: | Línea 53: | ||
*f. psq, predicado cuadrado: | *f. psq, predicado cuadrado: | ||
<math>psq(x) = (sqrt(x) \times sqrt(x) = x)</math> | <math>psq(x) = (sqrt(x) \times sqrt(x) = x)</math> | ||
</pre> | |||
==Ejercicio 03== | ==Ejercicio 03== | ||
Línea 59: | Línea 59: | ||
*2. Definimos la funcion auxiliar f1(x, 0) = x, f1(x, y + 1) = g(y, f1(x, y), x), donde g(x1, x2, x3) = x3^x2 . Ahora definimos f(0) = 0 y f(y + 1) = f1(y + 1, y + 1). | *2. Definimos la funcion auxiliar f1(x, 0) = x, f1(x, y + 1) = g(y, f1(x, y), x), donde g(x1, x2, x3) = x3^x2 . Ahora definimos f(0) = 0 y f(y + 1) = f1(y + 1, y + 1). | ||
<pre> | |||
*a) | *a) | ||
f(x,0) = 1 | f(x,0) = 1 | ||
Línea 82: | Línea 83: | ||
Como g es RP, H es RP y f es RP. | Como g es RP, H es RP y f es RP. | ||
</pre> | |||
==Ejercicio 04== | ==Ejercicio 04== | ||
Línea 88: | Línea 90: | ||
*3. Para empezar, podemos observar que f(x, 0) = φ(x, 0) y f(x, y + 1) = f(φ(x, y + 1), y). Lo que tendriamos que hacer es intercambiar el orden de f y de φ. Para eso, vamos a hacer un truquito. Definimos g(x1, x2, x3, x4) = φ(x2, x4 _o x1). Esta g es primitiva recursiva. Ahora, definimos f13 (x, y, 0) = φ(x, y), f13 (x, y, i + 1) = g(i, f13 (x, y, i), x, y) y vemos que f1 es primitiva recursiva. Ahora, f3(x, y) = f13(x, y, y). | *3. Para empezar, podemos observar que f(x, 0) = φ(x, 0) y f(x, y + 1) = f(φ(x, y + 1), y). Lo que tendriamos que hacer es intercambiar el orden de f y de φ. Para eso, vamos a hacer un truquito. Definimos g(x1, x2, x3, x4) = φ(x2, x4 _o x1). Esta g es primitiva recursiva. Ahora, definimos f13 (x, y, 0) = φ(x, y), f13 (x, y, i + 1) = g(i, f13 (x, y, i), x, y) y vemos que f1 es primitiva recursiva. Ahora, f3(x, y) = f13(x, y, y). | ||
<pre> | |||
*a | *a | ||
Línea 122: | Línea 125: | ||
<math>f(x,y) = g(x,y,y,y+1)</math> | <math>f(x,y) = g(x,y,y,y+1)</math> | ||
</pre> | |||
==Ejercicio 05== | ==Ejercicio 05== | ||
(para despues) | (para despues) | ||
<pre> | |||
*a) <math>f(x) = \sum_{i=0}^x (g(i) > 3)</math> | *a) <math>f(x) = \sum_{i=0}^x (g(i) > 3)</math> | ||
Línea 134: | Línea 138: | ||
donde el menos (-) es el menos con puntito arriba. | donde el menos (-) es el menos con puntito arriba. | ||
</pre> | |||
==Ejercicio 06== | ==Ejercicio 06== | ||
Línea 156: | Línea 161: | ||
*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. | ||