Recursión primitiva

En teoría de la computabilidad, la recursión primitiva permite definir una clase de funciones que forman un importante paso en la formalización de la noción de computabilidad, la clase de funciones recursivas primitivas. Se definen usando como principales operaciones la recursión y composición de funciones y forman un subconjunto estricto de las funciones recursivas, que son precisamente las funciones computables. Las funciones recursivas se definen agregándole a la recursión primitiva el operador de búsqueda no acotada que permite definir funciones parciales.

Muchas de las funciones normalmente estudiadas en teoría de los números, y las aproximaciones a las funciones de valor real utilizan la recursión primitiva. Como ejemplo de ellas se tiene la suma, la división, el factorial, el enésimo primo, etc. De hecho, no es fácil definir una función que sea recursiva pero que no se pueda definir con recursión primitiva.

La variable o argumento de una función recursiva primitiva es un número natural o una n-tupla de números naturales (i₁, i₂,..., i_n), mientras que el resultado o valor de la función es un número natural. Una función recursiva primitiva es n-aria si toma como argumento o variable n-uplas de números naturales. El conjunto de las funciones primitivas recursivas se define según las siguientes reglas:

1. Para todo k >= 0, la función cero k-aria definida como zero_k(n₁, n₂, ..., n_k) = 0, para todo número natural n₁, n₂, ..., n_k, es primitiva recursiva.
2. La función sucesor S, de aridad 1, que produce el siguiente entero según los axiomas de Peano, es primitiva recursiva.
3. Las funciones de proyección P_iⁿ, de aridad n que producen como resultado su argumento de la posición i son primitivas recursivas.
4. Composición: Dadas f, una función primitiva recursiva de aridad k, y g₁,...,g_k, funciones primitivas recursivas de aridad n, la composición de f con g₁,...,g_k, es decir, la función h(x₁,...,x_n) = f(g₁(x₁,...,x_n),...,g_k(x₁,...,x_n)), es primitiva recursiva.
5. Recursión primitiva: Dadas f, una función primitiva recursiva de aridad k, y g, una función primitiva recursiva de aridad k+2, la función h de aridad k+1 definida como h(0,x₁,...,x_k) = f(x₁,...,x_k) y h(S(n), x₁,...,x_k) = g(h(n, x₁,...,x_k), n, x₁,...,x_k), es primitiva recursiva.

Se puede notar que las funciones de proyección permiten contrarrestar la rigidez impuesta por la paridad de las funciones en la definición anterior, dado que en la composición se puede pasar cualquier subconjunto de los argumentos.

Una función es primitiva recursiva si es la función constante cero, la función sucesor, una proyección o si se define a partir de funciones primitivas recursivas utilizando únicamente composición y recursión primitiva.

Intuitivamente, se esperaría que la suma se comportase de la forma siguiente:

suma(0,x)=x

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

llevada esta función al esquema de las funciones primitivas queda así:

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

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

(donde P₁³ es la función que recibe tres argumentos y devuelve el primero de ellos)

Se puede ver que P₁¹ es la función identidad; se incluye su llamada para conformarse estrictamente al esquema de la recursión primitiva (función f del esquema). La composición de S con P₁³, en el segundo caso también corresponde al esquema dado anteriormente (función g del esquema).

Si bien la recursión primitiva parece poder expresar cualquier operación, en realidad solamente cubre un subconjunto estricto de las funciones computables. Esto se verifica con una variante del argumento de diagonalización de Cantor. La prueba se puede esquematizar como sigue:

Las funciones primitivas recursivas pueden ser ordenadas estrictamente asignándole a cada una de ellas un número. Este número es único para cada definición de función, si bien dos definiciones equivalentes de la misma función podrían tener diferente número asociado. El número asociado a cada función es calculable en el sentido de que puede ser definido mediante un mecanismo de cómputo como una función recursiva o una máquina de Turing.

Se construye ahora una matriz donde las filas son las funciones primitivas recursivas de un solo argumento en orden según el número asociado y las columnas son los naturales. El valor de cada casilla es el resultado de la función de esa fila para el valor entero de esa columna.

Se define ahora la función g(x) = S(n) donde n es el valor de la casilla de la fila y columna x. Cualquiera sea el valor de x, el valor de g(x) será distinto al de la función de la fila x al menos para el entero x. Por la construcción anterior, la función es computable, pero no recursiva primitiva, dado que es diferente a toda función primitiva para al menos un argumento entero. En conclusión, deben existir funciones computables que no son primitivas recursivas.

Este mismo argumento se puede utilizar para cualquier conjunto de funciones totales computables, por lo que cualquier enumeración (que pueda llevarse a cabo mediante un mecanismo de cómputo) de funciones computables totales es necesariamente incompleta. En cambio, las funciones parciales computables sí pueden ser enumeradas de forma completa, por ejemplo enumerando el «programa» de su correspondiente máquina de Turing.

Un ejemplo notable de función recursiva que no es primitiva recursiva es la función de Ackermann.

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