| Recursión primitiva de tipo 1 | Sean h:N->N y g:N2->N. Decimos que h se obtiene de g por RP de tipo 1 o tiene un esquema recursivo de tipo 1 (ERP1) si cumple:
-h(0) = k∈N
-h(n+1) = g(n, h(n)) |
| Recursión primitiva de tipo 2 | Sean g:Nn+2 -> N, f:Nn -> N funciones. Decimos que h:Nn+1 -> N se obtiene de recursión primitiva de tipo 2 de f y g (ERP2) si h cumple:
-h(x1,...,xn,0) = f(x1,...,xn)
-h(x1,...,xn,t+1) = g(x1,...,xn,t,h(x1,...,xn,t)) |
| Funciones iniciales | cero:N->N / cero(n)=0
suc:N->N / suc(n)=n+1
πin:Nn->N / πin(x1,...,xn)=xi (función proyección) |
| Función recursiva primitiva | Una función es recursiva primitiva si se obtiene por finitos pasos de las funciones iniciales a partir de composición, ERP1 y ERP2 |
| Predicado recursivo primitivo | Un predicado RP k-ario es una relación P⊆/Nk
Le podemos asignar su función característica
Cp(x1,...,xn) = |1 si (x1,...,xn)∈P
|0 si no |
