Recursión primitiva

En teoria de la computabilidad, la recursión primitiva permet definir una classe de funcions que formen un important pas en la formalisació de la noció de computabilidad, la classe de funcions recursivas primitives. Es definixen usant com a principals operacions la recursión i composició de funcions i formen un subconjunt estricte de les funcions recursivas, que són precisament les funcions computables. Les funcions recursivas es definixen agregant-li a la recursión primitiva l'operador de busca no acotada que permet definir funcions parcials.

Moltes de les funcions normalment estudiades en teoria dels números, i les aproximacions a les funcions de valor real utilisen la recursión primitiva. Com a eixemple d'elles es té la suma, la divisió, el factorial, l'enèsim primer, etc. De fet, no és fàcil definir una funció que siga recursiva pero que no es puga definir en recursión primitiva.

Definició

La variable o argument d'una funció recursiva primitiva és un número natural o una n-tupla d'número natural (i₁, i₂,..., i_n), mentres que el resultat o valor de la funció és un número natural. Una funció recursiva primitiva és n-ària si pren com a argument o variable n-uplas d'número natural. El conjunt de les funcions primitives recursivas es definix segons les següents regles:

1. Para tot k >= 0, la funció zero k-ària definida com zero_k(n₁, n₂, ..., n_k) = 0, per a tot número natural n₁, n₂, ..., n_k, és primitiva recursiva.
2. La funció successor S, de aridad 1, que produïx el següent sancer segons els axioma de Peano, és primitiva recursiva.
3. Les funcions de proyecció P_iⁿ, de aridad n que produïxen com resultat el seu argument de la posició i són primitives recursivas.
4. Composició: Donades f, una funció primitiva recursiva de aridad k, i g₁,...,g_k, funcions primitives recursivas de aridad n, la composició de f en g₁,...,g_k, és dir, la funció h(x₁,...,x_n) = f(g₁(x₁,...,x_n),...,g_k(x₁,...,x_n)), és primitiva recursiva.
5. Recursión primitiva: Donades f, una funció primitiva recursiva de aridad k, i g, una funció primitiva recursiva de aridad k+2, la funció h de aridad k+1 definida com a h(0,x₁,...,x_k) = f(x₁,...,x_k) i h(S(n), x₁,...,x_k) = g(h(n, x₁,...,x_k), n, x₁,...,x_k), és primitiva recursiva.

Es pot notar que les funcions de proyecció permeten contrarrestar la rigidea imposta per la paritat de les funcions en la definició anterior, ya que en la composició es pot passar qualsevol subconjunt dels arguments.

Una funció és primitiva recursiva si és la funció constant zero, la funció successor, una proyecció o si es definix a partir de funcions primitives recursivas utilisant únicament composició i recursión primitiva.

Eixemple

Suma de sancers

Intuitivament, s'esperaria que la suma es comportara de la forma següent:

suma(0,x)=x

suma(n+1,x)=suma(n, x)+1

duta esta funció a l'esquema de les funcions primitives queda aixina:

suma(0,x)=P₁¹(x)

suma(S(n), x)=S(P₁³(suma(n, x), n, x))

(a on P₁³ és la funció que rep tres arguments i torna el primer d'ells)

Es pot vore que P₁¹ és la funció identitat; s'inclou la seua cridada per a conformar-se estrictament a l'esquema de la recursión primitiva (funció f de l'esquema). La composició de S en P₁³, en el segon cas també correspon a l'esquema donat anteriorment (funció g de l'esquema).

Referències

Harry R. Lewis, Christos H. Papadimitriou, Elements of the theory of computation, Prentice-Hall, ISBN 0-13-262478-8