Recursión global
En la teoría de la computabilidad, la recursión global es una técnica para definir funciones aritméticas por recursión . En una definición de una función f por recursión global, el valor de f(n) se calcula a partir de la secuencia .
El hecho de que tales definiciones se puedan simplificar muestra que son recursivas primitivas. A diferencia de la recursión global, en la recursión primitiva el cálculo de una función requiere únicamente el valor anterior. Por ejemplo; para una función recursiva primitiva 1-aria g, el valor de g(n +1) se calcula solo a partir de g(n) y n .
Definición y ejemplos
La función factorial n! se define recursivamente por las reglas
Esta recursión es primitiva porque calcula el siguiente valor (n +1)! de la función utilizando el valor n y el valor anterior n! Por otro lado, la función Fib(n), que devuelve el n -ésimo número de Fibonacci, se define con las ecuaciones de recursión
Para calcular Fib(n+2), se requieren los dos últimos valores. Finalmente, considere la función g definida mediante las ecuaciones de recurrencia
Si bien los ejemplos anteriores utilizaban un número fijo de valores anteriores, g depende de un número variable de valores anteriories. En particular, g(n+1) requiere todos sus valores anteriores. Utilizando la Numeración de Gödel, podemos definir una función de recursión global como
donde es el número de Gödel que codifica la secuencia indicada.
- .
- ,
Equivalencia a recursión primitiva
Dada la función por recursión global f:
Basta con definir una función auxiliar para expresarla en un esquema de recursión primitiva
De este modo codifica los primeros n valores de f. La función es primitiva recursiva ya que se obtiene añadiendo a el nuevo elemento :
- ,
Utilizando , la función original f se puede definir por , lo que demuestra que también es una función recursiva primitiva.
Referencias
- Hinman, PG, 2006, Fundamentals of Mathematical Logic, AK Peters.
- Odifreddi, PG, 1989, Classical Recursion Theory, North Holland; second edition, 1999.