Revisión actual |
Tu texto |
Línea 1: |
Línea 1: |
| {{Back|Lógica y Computabilidad}}
| | ==Ej 4== |
| | |
| ==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 <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.
| |
| | |
| | |
| *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. 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:
| |
| | |
| <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. 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 <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 (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 | | *a |
|
| |
|
| f(0) = 0
| | <math>g(x,y) = \psi^(x) (y)</math> |
| | |
| <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(0,y) = y</math> |
| <math>g(x+1, y) = \psi(g(x,y))</math> | | <math>g(x+1, y) = \psi(g(x,y))</math> |
|
| |
|
| <math>f(x) = g(x,x) = \psi^{(x)}(x)</math> | | <math>f(x) = g(x,x) = \psi^(x) (x)</math> |
|
| |
|
| *b. Lo mismo pero con + 1 | | *b. Lo mismo pero con + 1 |
Línea 122: |
Línea 19: |
|
| |
|
| <math>f(x,y) = g(x,y,y,y+1)</math> | | <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.
| |
| <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.
| |
| 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,
| |
| <br>lg(0) = 0
| |
| <br>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.
| |
|
| |
|
| |
| [[Category:Prácticas]]
| |