Recursión primitiva

Recursión primitiva

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.

Contenido

Definición

La variable o argumento de una función recursiva primitiva es un número natural o una n-pla 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-plas de números naturales. El conjunto de las funciones primitivas recursivas se define según las siguientes reglas:

  1. La constante 0 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: Dado f, una función primitiva recursiva de aridad k y k funciones primitivas recursivas de aridad l g0,...,gk-1, la composición de f con g0,...,gk-1, es decir, la función h(x0,...,xl-1) = f(g0(x0,...,xl-1),...,gk-1(x0,...,xl-1)), es primitiva recursiva.
  5. Recursión primitiva: Dado f una función primitiva recursiva de aridad k y g una función primitiva recursiva de aridad k+2, la función de aridad k+1 definida como la función h donde h(0,x0,...,xk-1) = f(x0,...,xk-1) y h(S(n), x0,...,xk-1) = g(h(n, x0,...,xk-1), n, x0,...,xk-1), 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.

Ejemplo

Suma de enteros

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)=P1¹(x)
suma(S(n), x)=S(P1³(suma(n, x), n, x))

(donde P1³ es la función que recibe tres argumentos y retorna el primero de ellos)

Se puede ver que P1¹ 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 P1³, en el segundo caso también corresponde al esquema dado anteriormente (función g del esquema).


Limitaciones

Si bien la recursión primitiva parece poder expresar cualquier operación, en realidad sólo 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.

Obtenido de "Recursi%C3%B3n primitiva"

Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • 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… …   Enciclopedia Universal

  • Función de Ackermann — En teoría de la computación, la función de Ackermann es una función recursiva que toma dos números naturales como argumentos y devuelve un único número natural. Como norma general se define como sigue …   Wikipedia Español

  • Función recursiva — En lógica matemática y computación, las funciones recursivas o también conocidas como funciones recursivas μ son una clase de funciones de los números naturales en los números naturales que son «computables» en un sentido intuitivo. De hecho, en… …   Wikipedia Español

  • Scheme — Información general Paradigma multi paradigma Apareció en 1975 …   Wikipedia Español

  • Lógica matemática — La lógica matemática es una parte de la lógica y las matemáticas, que consiste en el estudio matemático de la lógica y en la aplicación de este estudio a otras áreas de las matemáticas. La lógica matemática tiene estrechas conexiones con la… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”