Recursión global

En la teoria de la computabilidad, la recursión global és una tècnica per a definir funcions aritmètiques per recursión . En una definició d'una funció f per recursión global, el valor de f(n) es calcula a partir de la seqüència $⟨f(0),f(1),\dots ,f(n-1)⟩$ .

El fet de que tals definicions es puguen simplificar mostra que són recursivas primitives. A diferència de la recursión global, en la recursión primitiva el càlcul d'una funció requerix únicament el valor anterior. Per eixemple; per a una funció recursiva primitiva 1-ària g, el valor de g(n +1) es calcula solament a partir de g(n) i n .

Definició i eixemples

La funció factorial n! es definix recursivamente per les regles

$0!=1,$

$(n+1)!=n!(n+1).$

Esta recursión és primitiva perque calcula el següent valor (n +1)! de la funció utilisant el valor n i el valor anterior n! Per un atre costat, la funció Fib(n), que torna el n -ésimo número de Fibonacci, es definix en les equacions de recursión

$Fib(0)=0,$

$Fib(1)=1,$

$Fib(n+2)=Fib(n+1)+Fib(n).$

Per a calcular Fib(n+2), es requerixen els dos últims valors. Finalment, considere la funció g definida per mig de les equacions de recurrencia

$g(0)=0,$

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

Si ben els eixemples anteriors utilisaven un número fix de valors anteriors, g depén d'un número variable de valors anteriories. En particular, g(n+1) requerix <o>tots</o> els seus valors anteriors. Utilisant la Numeració de Gödel, podem definir una funció de recursión global com

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

a on $⟨f(0),f(1),\dots ,f(n-1)⟩$ és el número de Gödel que codifica la seqüència 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))),$

Equivalència a recursión primitiva

Donada la funció per recursión global f:

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

N'hi ha prou en definir una funció auxiliar per a expressar-la en un esquema de recursión primitiva

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

D'esta manera $\overline{f}(n)$ codifica els primers n valores de f. La funció $\overline{f}$ és primitiva recursiva ya que $\overline{f}(n+1)$ s'obté afegint a $\overline{f}(n)$ el nou element $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))$

Utilisant $\overline{f}$, la funció original f es pot definir per $f(n)=\overline{f}(n+1)[n]$, lo que demostra que també és una funció recursiva primitiva.

Referències

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