Ejercicio 6
Una clase de funciones C es PRC si contiene las funciones iniciales y está cerrada por composición y recursión primitiva.
Podemos afirmar que una función cualquiera va a estar en toda clase PRC si podemos demostrar que pertenece a la clase
3 ues no existe k P N para satisfacer los otros 2 casos cuando t “ 0.
hpx1, . . . , xn, 0q “ fpx1, . . . , xnq
Para el caso t ą 0 primero reescribimos la función por casos colocando t`1 en donde antes teńıamos t para poder ajustarnos al esquema de recursión primitiva.
hpx1, . . . , xn, t` 1q “
#
g1px1, . . . , xn, k, hpx1, . . . , xn, t` 1´ 1qq si t` 1 “ 2 ¨ k ` 1
g2px1, . . . , xn, k, hpx1, . . . , xn, t` 1´ 1qq si t` 1 “ 2 ¨ k ` 2
“
#
g1px1, . . . , xn, k, hpx1, . . . , xn, tqq si t “ 2 ¨ k
g2px1, . . . , xn, k, hpx1, . . . , xn, tqq si t “ 2 ¨ k ` 1
Ahora necesitamos despejar k en función de t.
t “ 2 ¨ k ñ k “ tt{2u “ div2ptq
t “ 2 ¨ k ` 1 ñ k “ tpt´ 1q{2u “ div2pt´ 1q “ div2ptq pues t es impar y div2 redondea hacia abajo
Reescribimos h eliminando por completo la k.
hpx1, . . . , xn, t` 1q “
#
g1px1, . . . , xn,div2ptq, hpx1, . . . , xn, tqq si parptq
g2px1, . . . , xn,div2ptq, hpx1, . . . , xn, tqq si imparptq
También podemos escribir h como suma de cada caso por su predicado.
4 hpx1, . . . , xn, t` 1q “ g1px1, . . . , xn,div2ptq, hpx1, . . . , xn, tqq ¨ parptq ` g2px1, . . . , xn,div2ptq, hpx1, . . . , xn, tqq ¨ imparptq
Conclusión
h sigue el esquema de recursión primitiva.
h compone funciones que están en C (puntualmente f , g1 y g2).
h compone funciones que están en toda clase PRC (puntualmente div2, par, impar).
C es una clase PRC por el enunciado, entonces contiene a las funciones div2, par, impar.
Por lo tanto cualquier h que cumpla con este esquema pertenece a C.