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. 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.

Definición

La variable o argumento de una función recursiva primitiva es un número natural o una n-tupla de números naturales (i1, i2,..., in), 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 zerok(n1, n2, ..., nk) = 0, para todo número natural n1, n2, ..., nk, 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 Pin, 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 g1,...,gk, funciones primitivas recursivas de aridad n, la composición de f con g1,...,gk, es decir, la función h(x1,...,xn) = f(g1(x1,...,xn),...,gk(x1,...,xn)), 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,x1,...,xk) = f(x1,...,xk) y h(S(n), x1,...,xk) = g(h(n, x1,...,xk), n, x1,...,xk), 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.

Other Languages