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 | *2. Si tomamos hpxq � pxq y gpx1, x2, x3q � u32 px1, x2, x3q 'px3, x1q, se ve que ambas son totales. Ahora, podemos reescribir fpx, 0q � hpxq y fpx, y1q � gpy, fpx, yq, xq, con lo cual, nos habian dado una definicion por recursion primitiva. | ||
*3. Si tomamos | *3. Si tomamos hpxq � 'p0, xq y gpx1, x2, x3q � 'px2, spx1q, se ve que ambas son totales. Ahora, podemos reescribir fpx, 0q � hpxq y fpx, y 1q � gpy, fpx, yq, xq, 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== | ||
*1. | *1. m´axpx, yq � y px � yq | ||
*2. | *2. m´ınpx, yq � x � px � yq | ||
*3. Para resolver esto, observemos que un | *3. Para resolver esto, observemos que un n´umero es par si y s´olo si su antecesor no lo es. Entonces, definimos parp0q � 1, parpy 1q � 1 � parpyq. | ||
*4. | *4. hfp0q � 0, hfpy 1q � p1 hfpyqqp1 � parpyqq hfpyqparpyq. | ||
*5. | *5. sqrtpxq � m´ın {0¤i¤x} ppi 1q2 ¡ xq | ||
*6. | *6. psqpxq � psqrtpxq � xq. | ||
<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== | ||
*1. | *1. fpx, 0q � px � 0qxpx � 0q, fpx, y1q � gpy, fpx, yq, xq, donde gpx1, x2, x3q � px3 � 0qpx3�x2qpx3 � 0q. | ||
*2. Definimos la | *2. Definimos la funci´on auxiliar f1px, 0q � x, f1px, y 1q � gpy, f1px, yq, xq, donde gpx1, x2, x3q � xx23 . Ahora definimos fp0q � 0 y fpy 1q � f1py 1, y 1q. | ||
<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== | ||
*1. Podemos definir f11 | *1. Podemos definir f11 px, 0q � x, f11 px, y 1q � gpy, f11px, yq, xq, donde gpx1, x2, x3q � px2q. As´ı, f1pxq � f11 px, xq. | ||
*2. Podemos definir f12 | *2. Podemos definir f12 px, 0q � pxq px � 0q, f12px, y 1q � gpy, f12 | ||
*3. Para empezar, podemos observar que | px, yq, xq, donde gpx1, x2, x3q � px2q 1. As´ı, f2pxq � f12 px, xq. | ||
*3. Para empezar, podemos observar que fpx, 0q � 'px, 0q y fpx, y 1q � fp'px, y 1q, yq. Lo que tendr´ıamos que hacer es intercambiar el orden de f y de '. Para eso, vamos a hacer un truquito. Definimos gpx1, x2, x3, x4q � 'px2, x4 � x1q. Esta g es primitiva recursiva. Ahora, definimos f13 px, y, 0q � 'px, yq, f13 px, y, i 1q � gpi, f13 px, y, iq, x, yq y vemos que f1 es primitiva recursiva. Ahora, f3px, yq � f13 | |||
px, y, yq. | |||
<pre> | |||
*a | *a | ||
Línea 122: | Línea 127: | ||
<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 140: | ||
donde el menos (-) es el menos con puntito arriba. | donde el menos (-) es el menos con puntito arriba. | ||
</pre> | |||
==Ejercicio 06== | ==Ejercicio 06== | ||
*1. | *1. | ||
fpx1, . . . , xn, 0q � gpx1, . . . , xn, 0q fpx1, . . . , xn, y 1q � pgpx1, . . . , xn, y 1q fpx1, . . . , xn, yqqfpx1, . . . , xn, yq pgpx1, . . . , xn, y 1q ¥ fpx1, . . . , xn, yqqgpx1, . . . , xn, y 1q | |||
*2. | *2. | ||
fpx1, . . . , xn, yq � pbpyq ¤ tpyqqp m´ax 0¤i¤tpyq rpbpyq ¤ iqgpx1, . . . , xn, yqsq | |||
==Ejercicio 07== | ==Ejercicio 07== | ||
Para usar la sugerencia, notemos que | Para usar la sugerencia, notemos que x2 ¤ 2 ô x2 �10n ¤ 2�10n. Con esta observaci´on, vemos que gpnq � m´ax {0¤i¤2�10n} i � pi2 � 10n ¤ 2 � 10nq. Ahora, hpnq � restopgpnq, 10q. | ||
==Ejercicio 08== | ==Ejercicio 08== | ||
*1. | *1. shrpx, nq � hfnpxq, donde hf se defini´o en el ejercicio 1, inciso 4, y aplicar n veces se defini´o en el ejercicio 4, inciso 1. | ||
*2. | *2. lgpxq no es m´as que la cantidad de d´ıgitos binario de x. Entonces, | ||
lgp0q � 0 lgpy 1q � m´ax 0¤i¤y1 pshrpx, iq � 0q � i *3. digpx, nq � 1 � parpshrpx, nqq. | |||
*4. wgtpxq � ¸ 0¤i¤lgpxq digpx, iq *5. Asumiendo que el primer d´ıgito es el menos significativo, ldpxq � restopx, 10q. | |||
*3. | *6. En la te´orica se ve como construir r x y s. Con eso, tendr´ıamos una shr10. Con ella podemos definir un lg10, y dig10. Con esto, fdpxq � digpx, lg10pxqq. | ||
*4. | *7. Prpx, yq � °x¤i¤y primopiq, donde primo es la f.p.r. que nos dice si un n´umero es primo. | ||
*5. Asumiendo que el primer | *8. Basta definir Gpx, yq � f11 px, yq, donde f11 se defini´o en el inciso 1 del ejercicio 4. | ||
*6. En la | |||
*7. | |||
*8. Basta definir | |||