Fonction de Sudan

En calculabilité, la fonction de Sudan est un exemple de fonction récursive mais non récursive primitive (de même que la fonction d'Ackermann, plus connue).

Elle fut conçue en 1927 par le mathématicien roumain Gabriel Sudan, élève de David Hilbert.

Définition

,
,
.

Tableaux de valeurs

Valeurs de F0(x, y) = x + y
y\x 0 1 2 3 4 5
0 012345
1 123456
2 234567
3 345678
4 456789
5 5678910
6 67891011
Valeurs de F1(x, y)
y\x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 01234567891011121314
1 1357911131517192123252729
2 4812162024283236404448525660
3 111927354351596775839199107115123
4 2642587490106122138154170186202218234250
5 5789121153185217249281313345377409441473505
6 1201842483123764405045686326967608248889521016
7 247375503631759887101511431271139915271655178319112039
8 5027581014127015261782203822942550280630623318357438304086
9 101315252037254930613573408545975109562161336645715776698181
10 2036306040845108613271568180920410228112521227613300143241534816372
11 408361318179102271227514323163711841920467225152456326611286593070732755
12 81781227416370204662456228658327543685040946450424913853234573306142665522
13 1636924561327534094549137573296552173713819059009798289106481114673122865131057
14 3275249136655208190498288114672131056147440163824180208196592212976229360245744262128

On peut démontrer que F1(x, y) = F1(0, y) + 2y x.

Valeurs de F2(x, y)
y\x 0 1 2 3 4 5
0 012345
1 182774185440
2 19F1(8, 10) = 10 228F1(27, 29) = 15 569 256 417 ≈ 1,55.1010 F1(74, 76) ≈ 5,74.1024 F1(185, 187) ≈ 3,67.1058 F1(440, 442) ≈ 5,02.10135

Voir aussi

Article connexe

Algorithme récursif

Liens externes

Suites A260003 et A260004 de l'OEIS

Crédit d'auteurs

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Sudan function » (voir la liste des auteurs).
  • Portail de la logique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.