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 ${\displaystyle \langle f(0),f(1),\ldots ,f(n-1)\rangle }$ .

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 .

La función factorial n! se define recursivamente por las reglas

${\displaystyle 0!=1,}$

${\displaystyle (n+1)!=n!(n+1).}$

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

${\displaystyle Fib(0)=0,}$

${\displaystyle Fib(1)=1,}$

${\displaystyle Fib(n+2)=Fib(n+1)+Fib(n).}$

Para calcular Fib(n+2), se requieren los dos últimos valores. Finalmente, considere la función g definida mediante las ecuaciones de recurrencia

${\displaystyle g(0)=0,}$

${\displaystyle g(n+1)=\sum _{i=0}^{n}g(i)^{n-i}.}$

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

${\displaystyle f(n)=h(n,\langle f(0),f(1),\ldots ,f(n-1)\rangle )}$

donde ${\displaystyle \langle f(0),f(1),\ldots ,f(n-1)\rangle }$ es el número de Gödel que codifica la secuencia indicada.

${\displaystyle f(n)=h(n,\langle f(0),f(1),\ldots ,f(n-1)\rangle )}$ .

${\displaystyle {\bar {f}}(0)=\langle \rangle }$ ,

${\displaystyle {\bar {f}}(n+1)={\mathit {a{\tilde {n}}adir}}(n,{\bar {f}}(n),h(n,{\bar {f}}(n))),}$

Dada la función por recursión global f:

${\displaystyle {\bar {f}}(n)=\langle f(0),f(1),\ldots ,f(n-1)\rangle }$

Basta con definir una función auxiliar para expresarla en un esquema de recursión primitiva

${\displaystyle {\bar {f}}(n)=\langle f(0),f(1),\ldots ,f(n-1)\rangle }$

De este modo ${\displaystyle {\bar {f}}(n)}$ codifica los primeros n valores de f. La función ${\displaystyle {\bar {f}}}$ es primitiva recursiva ya que ${\displaystyle {\bar {f}}(n+1)}$ se obtiene añadiendo a ${\displaystyle {\bar {f}}(n)}$ el nuevo elemento ${\displaystyle h(n,{\bar {f}}(n))}$ :

${\displaystyle {\bar {f}}(0)=\langle \rangle }$ ,

${\displaystyle {\bar {f}}(n+1)={\mathit {append}}(n,{\bar {f}}(n),h(n,{\bar {f}}(n))),}$

${\displaystyle {\bar {f}}(n+1)=g(n,{\bar {f}}(n))}$

Utilizando ${\displaystyle {\bar {f}}}$, la función original f se puede definir por ${\displaystyle f(n)={\bar {f}}(n+1)[n]}$, lo que demuestra que también es una función recursiva primitiva.

• Hinman, PG, 2006, Fundamentals of Mathematical Logic, AK Peters.
• Odifreddi, PG, 1989, Classical Recursion Theory, North Holland; second edition, 1999.