Ejercicio 01
- 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
- 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.
par(0) = 1
par(t+1) = 1 - par(t)
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
f(x,0) = 1
f(x, y+1) = g(x,y,f(x,y))
con g(x,y,z) = z * x
Definimos
m veces
notar que
Vemos que H es RP:
con
Como g es RP, H es RP y f es RP.
Ejercicio 04
f(0) = 0
Sea
definida por recursión como:
H(n,0) = 1
con
g es RP -> H es RP -> f es RP
Otra resulución:
g(x,y,z,0) = x
- es el menos natural (con puntito arriba)
Ejercicio 05
- a)
![{\displaystyle f(x)=\sum _{i=0}^{x}(g(i)>3)}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/2d4b0caf4a508100621bf233b0f2ae6c97c1f8a9)
- b)
![{\displaystyle f(x,y)=\prod _{i=y}^{x}(g(i+1)>g(i))}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/0add7d328cf3044e75582ad4960b963ea8e2757b)
- c)
![{\displaystyle f(x,y,w)=\alpha (x-y)\times \prod _{i=x}^{y}(w\geq g(i))}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/947bf14cc3b4b65e1c77df29b9e6e158de9fddd4)
donde el menos (-) es el menos con puntito arriba.
Ejercicio 06
Ejercicio 07
Ejercicio 08