Diferencia entre revisiones de «Práctica 8: Funciones Primitivas Recursivas (Lógica y Computabilidad)»

De Cuba-Wiki
Sin resumen de edición
 
(No se muestran 16 ediciones intermedias de 3 usuarios)
Línea 1: Línea 1:
{{Back|Lógica y Computabilidad}}
==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 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.
*2. Si tomamos h(x) = ψ(x) y <math>g(x1, x2, x3) = u^{3}_{2} (x1, x2, x3) + φ(x3, x1)</math>, 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) = &psi;(x) y <math>g(x,y,z) = z + \varphi</math>.
*b) Si. Sea h(x) = &psi;(x) y <math>g(x,y,z) = z + \varphi</math>.


f(x,0) = h(x)
          f(x,0) = h(x)


f(x, y + 1) = g(x,y,f(x,y))
          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,0) = h(x)


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


==Ejercicio 02==
==Ejercicio 02==
Línea 28: Línea 29:
*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 53: Línea 54:
*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. fpx, 0q � px � 0q􀀀xpx � 0q, fpx, y􀀀1q � gpy, fpx, yq, xq, donde gpx1, x2, x3q � px3 � 0qpx3�x2q􀀀px3 � 0q.
*1. f(x, 0) = (x = 0)+x(x != 0), f(x, y+1) = g(y, f(x, y), x), donde g(x1, x2, x3) = (x3 != 0)(x3 x x2)+(x3 = 0).
*2. Definimos la funcion 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.
*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 83: Línea 82:


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 px, 0q � x, f11 px, y 􀀀 1q � gpy, f11px, yq, xq, donde gpx1, x2, x3q �  px2q. Ası, f1pxq � f11 px, xq.
*1. Podemos definir f11 (x, 0) = x, f11 (x, y + 1) = g(y, f11(x, y), x), donde g(x1, x2, x3) = ψ(x2). Asi, f1(x) = f11 (x, x).
*2. Podemos definir f12 px, 0q �  pxq 􀀀 px � 0q, f12px, y 􀀀 1q � gpy, f12
*2. Podemos definir f12 (x, 0) = ψ(x) + (x != 0), f12(x, y + 1) = g(y, f12(x, y), x), donde g(x1, x2, x3) = ψ(x2) + 1. Asi, f2(x) = f12 (x, x).
px, yq, xq, donde gpx1, x2, x3q �  px2q 􀀀 1. Ası, f2pxq � f12 px, xq.
*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 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 127: Línea 122:


<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 140: Línea 134:


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
<br>f(x1, .. , xn, 0) = g(x1, .. , xn, 0)
<br>f(x1, .. , xn, y + 1) = (g(x1, .. , xn, y + 1) < f(x1, .. , xn, y))f(x1, .. , xn, y) +(g(x1, .. , xn, y + 1) >= f(x1, .. , xn, y))g(x1, .. , xn, y + 1)
*2.
*2.
fpx1, . . . , xn, yq � pbpyq ¤ tpyqqp max 0¤i¤tpyq rpbpyq ¤ iqgpx1, . . . , xn, yqsq
f(x1, .. , xn, y) = (b(y) <= t(y))( max {0<=i<=t(y)} [ r(b(y) <= i)g(x1, .. , xn, y) ] )


==Ejercicio 07==
==Ejercicio 07==
Para usar la sugerencia, notemos que x2 ¤ 2 ô x2 �10n ¤ 2�10n. Con esta observacion, vemos que gpnq � max {0¤i¤2�10n} i � pi2 � 10n ¤ 2 � 10nq. Ahora, hpnq � restopgpnq, 10q.
Para usar la sugerencia, notemos que x^2 <= 2 <=> x^2 x 10^n <= 2 x 10^n. Con esta observacion, vemos que g(n) = max {0<=i<=2 x 10^n} i x (i^2 x 10^n <= 2 x 10^n). Ahora, h(n) = resto(g(n), 10).


==Ejercicio 08==
==Ejercicio 08==
*1. shrpx, nq � hfnpxq, donde hf se definio en el ejercicio 1, inciso 4, y aplicar n veces se definio en el ejercicio 4, inciso 1.
*1. shr(x, n) = hf^n(x), donde hf se definio en el ejercicio 1, inciso 4, y aplicar n veces se definio en el ejercicio 4, inciso 1.
*2. lgpxq no es mas que la cantidad de dıgitos binario de x. Entonces,
*2. lg(x) no es mas que la cantidad de digitos binarios de x. Entonces,
lgp0q � 0 lgpy 􀀀 1q � max 0¤i¤y􀀀1 pshrpx, iq � 0q � i *3. digpx, nq � 1 � parpshrpx, nqq.
<br>lg(0) = 0
*4. wgtpxq � ¸ 0¤i¤lgpxq digpx, iq *5. Asumiendo que el primer dıgito es el menos significativo, ldpxq � restopx, 10q.
<br>lg(y + 1) = max 0<=i<=y+1 (shr(x, i) != 0) x i
*6. En la teorica 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.
*3. dig(x, n) = 1 _o par(shr(x, n)).
*7. Prpx, yq � °x¤i¤y primopiq, donde primo es la f.p.r. que nos dice si un numero es primo.
*4. wgt(x) = Σ {0<=i<=lg(x)} dig(x, i)
*8. Basta definir Gpx, yq � f11 px, yq, donde f11 se definio en el inciso 1 del ejercicio 4.
*5. Asumiendo que el primer digito es el menos significativo, ld(x) = resto(x, 10).
*6. En la teorica se ve como construir [ x/y ]. Con eso, tendriamos una shr10. Con ella podemos definir un lg10, y dig10. Con esto, fd(x) = dig(x, lg10(x)).
*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.
 
 
[[Category:Prácticas]]

Revisión actual - 15:53 20 jul 2018

Plantilla:Back

Ejercicio 01

  • 1. Esta definicion no es por recursion primitiva: la llamada recursiva DEBE ser con x e y.
  • 2. Si tomamos h(x) = ψ(x) y Error al representar (error de sintaxis): {\displaystyle g(x1, x2, x3) = u^{3}_{2} (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.


  • 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 .
          f(x,0) = h(x)
          f(x, y + 1) = g(x,y,f(x,y))
  • c) Si. Sea y .
          f(x,0) = h(x)
          f(x, y + 1) = g(x,y,f(x,y))

Ejercicio 02

  • 1. max(x, y) = y + (x _o y)
  • 2. min(x, y) = x - (x _o y)
  • 3. Para resolver esto, observemos que un numero es par si y solo si su antecesor no lo es. Entonces, definimos par(0) = 1, par(y + 1) = 1 _o par(y).
  • 4. hf(0) = 0, hf(y + 1) = (1 + hf(y))(1 _o par(y)) + hf(y)par(y).
  • 5. sqrt(x) = min {0<=i<=x} ((i + 1)^2 > x)
  • 6. psq(x) = (sqrt(x) = x).


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

  • f. psq, predicado cuadrado:

Ejercicio 03

  • 1. f(x, 0) = (x = 0)+x(x != 0), f(x, y+1) = g(y, f(x, y), x), donde g(x1, x2, x3) = (x3 != 0)(x3 x x2)+(x3 = 0).
  • 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).
  • a)

f(x,0) = 1

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

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

  • b)

Definimos m veces

notar que

Vemos que H es RP:

con

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

Ejercicio 04

  • 1. Podemos definir f11 (x, 0) = x, f11 (x, y + 1) = g(y, f11(x, y), x), donde g(x1, x2, x3) = ψ(x2). Asi, f1(x) = f11 (x, x).
  • 2. Podemos definir f12 (x, 0) = ψ(x) + (x != 0), f12(x, y + 1) = g(y, f12(x, y), x), donde g(x1, x2, x3) = ψ(x2) + 1. Asi, f2(x) = f12 (x, x).
  • 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).
  • a

f(0) = 0

Sea definida por recursión como:

H(n,0) = 1

con

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

Otra resolución:

  • b. Lo mismo pero con + 1
  • c

g(x,y,z,0) = x

- es el menos natural (con puntito arriba)

Ejercicio 05

(para despues)


  • a)
  • b)
  • c)

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

Ejercicio 06

  • 1.


f(x1, .. , xn, 0) = g(x1, .. , xn, 0)
f(x1, .. , xn, y + 1) = (g(x1, .. , xn, y + 1) < f(x1, .. , xn, y))f(x1, .. , xn, y) +(g(x1, .. , xn, y + 1) >= f(x1, .. , xn, y))g(x1, .. , xn, y + 1)

  • 2.

f(x1, .. , xn, y) = (b(y) <= t(y))( max {0<=i<=t(y)} [ r(b(y) <= i)g(x1, .. , xn, y) ] )

Ejercicio 07

Para usar la sugerencia, notemos que x^2 <= 2 <=> x^2 x 10^n <= 2 x 10^n. Con esta observacion, vemos que g(n) = max {0<=i<=2 x 10^n} i x (i^2 x 10^n <= 2 x 10^n). Ahora, h(n) = resto(g(n), 10).

Ejercicio 08

  • 1. shr(x, n) = hf^n(x), donde hf se definio en el ejercicio 1, inciso 4, y aplicar n veces se definio en el ejercicio 4, inciso 1.
  • 2. lg(x) no es mas que la cantidad de digitos binarios de x. Entonces,


lg(0) = 0
lg(y + 1) = max 0<=i<=y+1 (shr(x, i) != 0) x i

  • 3. dig(x, n) = 1 _o par(shr(x, n)).
  • 4. wgt(x) = Σ {0<=i<=lg(x)} dig(x, i)
  • 5. Asumiendo que el primer digito es el menos significativo, ld(x) = resto(x, 10).
  • 6. En la teorica se ve como construir [ x/y ]. Con eso, tendriamos una shr10. Con ella podemos definir un lg10, y dig10. Con esto, fd(x) = dig(x, lg10(x)).
  • 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.