Funkcja Sudana

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

${\displaystyle F_{0}(x,y)=x+y,}$

${\displaystyle F_{n+1}(x,0)=x,\quad n\geqslant 0}$

${\displaystyle F_{n+1}(x,y+1)=F_{n}(F_{n+1}(x,y),F_{n+1}(x,y)+y+1),\quad n\geqslant 0.}$