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

Definición y ejemplos

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

$0!=1,$

$(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

$Fib(0)=0,$

$Fib(1)=1,$

$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

$g(0)=0,$

$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

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

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

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

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

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

Equivalencia a recursión primitiva

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

${\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

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

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

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

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

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

Utilizando ${\bar {f}}$, la función original f se puede definir por $f(n)={\bar {f}}(n+1)[n]$, 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.