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 $⟨f(0),f(1),\dots ,f(n-1)⟩$ .

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,⟨f(0),f(1),\dots ,f(n-1)⟩)$

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

$f(n)=h(n,⟨f(0),f(1),\dots ,f(n-1)⟩)$ .

$\overline{f}(0)=⟨⟩$ ,

$\overline{f}(n+1)=𝑎\widetilde{𝑛}𝑎𝑑𝑖𝑟(n,\overline{f}(n),h(n,\overline{f}(n))),$

Equivalencia a recursión primitiva

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

$\overline{f}(n)=⟨f(0),f(1),\dots ,f(n-1)⟩$

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

$\overline{f}(n)=⟨f(0),f(1),\dots ,f(n-1)⟩$

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

$\overline{f}(0)=⟨⟩$ ,

$\overline{f}(n+1)=𝑎𝑝𝑝𝑒𝑛𝑑(n,\overline{f}(n),h(n,\overline{f}(n))),$

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

Utilizando $\overline{f}$, la función original Plantilla:Math se puede definir por $f(n)=\overline{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.