Funkcja Sudana – Wikipedia, wolna encyklopedia

Ten artykuł od 2013-05 wymaga zweryfikowania podanych informacji.

Należy podać wiarygodne źródła w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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ść.

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