Funkcja Sudana

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj | edytuj kod]

F _0 (x, y) = x+y,\,
F _{n+1} (x, 0) = x, \quad  n \geqslant 0\,
F _{n+1} (x, y+1) = F _n (F_{n+1} (x, y), F_{n+1} (x, y) + y + 1), \quad n\geqslant 0.\,