Funkcja Sudana

Szablon:Dopracować Funkcja Sudana – występujący w teorii obliczeń przykład (obok bardziej znanej funkcji Ackermanna) funkcji będącej funkcją rekurencyjną, ale nie pierwotnie rekurencyjną.

Jej definicja została opublikowana w 1927 roku przez rumuńskiego matematyka Gabriela Sudana (ucznia Hilberta) i była pierwszą opublikowaną funkcją posiadającą wymienioną w powyższym akapicie własność.

Definicja

$F_0(x,y)=x+y,$

$F_{n+1}(x,0)=x,n⩾0$

$F_{n+1}(x,y+1)=F_n(F_{n+1}(x,y),F_{n+1}(x,y)+y+1),n⩾0.$