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 3: | Línea 3: | ||
==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. | ||
Línea 88: | Línea 88: | ||
*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 123: | ||
<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 136: | ||
donde el menos (-) es el menos con puntito arriba. | donde el menos (-) es el menos con puntito arriba. | ||
</pre> | |||
==Ejercicio 06== | ==Ejercicio 06== |