Práctica 8: Funciones Primitivas Recursivas (Lógica y Computabilidad)

Ejercicio 01

• 1. Esta definici´on no es por recursi´on primitiva: la llamada recursiva DEBE ser con x e y.
• 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, y􀀀1q � gpy, fpx, yq, xq, con lo cual, nos hab´ıan dado una definici´on por recursi´on primitiva.
• 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 hab´ıan dado una definici´on por recursi´on primitiva.

*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>.

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>.

f(x,0) = h(x)

f(x, y + 1) = g(x,y,f(x,y))

Ejercicio 02

• 1. m´axpx, yq � y 􀀀 px � yq
• 2. m´ınpx, yq � x � px � yq
• 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. hfp0q � 0, hfpy 􀀀 1q � p1 􀀀 hfpyqqp1 � parpyqq 􀀀 hfpyqparpyq.
• 5. sqrtpxq � m´ın {0¤i¤x} ppi 􀀀 1q2 ¡ xq
• 6. psqpxq � psqrtpxq � xq.

*a. Defino máximo recursivamente como:
 max(x,0) = x
 max(x,y+1) = 1 + max(p(x), y)

donde p(x) es la función primitiva recursiva ''predecesor''.

*b. Mínimo:

*c. Par:

 par(0) = 1
 par(t+1) = 1 - par(t)

*d. Hf (half):

 hf(0) = 0
 hf(t+1) = par(t) . hf(t) + [1 - par(t)] . [hf(t) + 1]

*e. Sqrt, raiz cuadrada entera:

<math>sqrt(x) = min_{0 \le i \le x}(i \times i > x) - 1 </math>

*f. psq, predicado cuadrado:
<math>psq(x) = (sqrt(x) \times sqrt(x) = x)</math>

Ejercicio 03

• 1. fpx, 0q � px � 0q􀀀xpx � 0q, fpx, y􀀀1q � gpy, fpx, yq, xq, donde gpx1, x2, x3q � px3 � 0qpx3�x2q􀀀px3 � 0q.
• 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.

*a)
f(x,0) = 1

f(x, y+1) = g(x,y,f(x,y))

con g(x,y,z) = z * x

*b) 
Definimos <math>H(n,m) = n^{n^{.^{.^{n}}}}</math>  m veces
<math>
H(n,0) = 0</math>

notar que <math>f(n) = H(n,n)</math>

Vemos que H es RP:

<math>H(n,0) = 0</math>

<math>H(n, m+1) = n^{H(n,m)} = g(n,m,H(n,m))</math>

con <math>g(n,m,p) = n^p</math>

Como g es RP, H es RP y f es RP.

Ejercicio 04

• 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 px, 0q � pxq 􀀀 px � 0q, f12px, y 􀀀 1q � gpy, f12

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.

*a

f(0) = 0

<math>f(n) = \psi^n(n) = H(n,n)</math>

Sea <math>H(n,m) = \psi^m(n)</math> definida por recursión como:

H(n,0) = 1

<math>H(n,m+1) = \psi^{H(n,m)}(n) = g(n,m,H(n,m))</math>

con <math>g(n,m,p) = \psi^p(n)</math>

g es RP -> H es RP -> f es RP

Otra resolución:
<math>g(x,y) = \psi^{(x)}(y)</math>

<math>g(0,y) = y</math>
<math>g(x+1, y) = \psi(g(x,y))</math>

<math>f(x) = g(x,x) = \psi^{(x)}(x)</math>

*b. Lo mismo pero con + 1

*c

g(x,y,z,0) = x
<math>g(x,y,z, w+1) = \phi(g(x,y,z,w), z - x)</math>

- es el menos natural (con puntito arriba)

<math>f(x,y) = g(x,y,y,y+1)</math>

Ejercicio 05

(para despues)

*a) <math>f(x) = \sum_{i=0}^x (g(i) > 3)</math>

*b) <math>f(x,y) = \prod_{i=y}^x (g(i+1) > g(i))</math>

*c) <math>f(x,y,w) = \alpha(x-y) \times \prod_{i=x}^y (w \ge g(i))</math>

donde el menos (-) es el menos con puntito arriba.

Ejercicio 06

• 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.

fpx1, . . . , xn, yq � pbpyq ¤ tpyqqp m´ax 0¤i¤tpyq rpbpyq ¤ iqgpx1, . . . , xn, yqsq

Ejercicio 07

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

• 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. lgpxq no es m´as que la cantidad de d´ıgitos binario de x. Entonces,

lgp0q � 0 lgpy 􀀀 1q � m´ax 0¤i¤y􀀀1 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.
• 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.
• 7. Prpx, yq � °x¤i¤y primopiq, donde primo es la f.p.r. que nos dice si un n´umero es primo.
• 8. Basta definir Gpx, yq � f11 px, yq, donde f11 se defini´o en el inciso 1 del ejercicio 4.