Fonction de Sudan

Un article de Wikipédia, l'encyclopédie libre.
Ceci est la version actuelle de cette page, en date du 23 mai 2019 à 09:19 et modifiée en dernier par Nomdutilisateur69 (discuter | contributions). L'URL présente est un lien permanent vers cette version.
(diff) ← Version précédente | Voir la version actuelle (diff) | Version suivante → (diff)

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[modifier | modifier le code]

,
,
.

Tableaux de valeurs[modifier | modifier le code]

Valeurs de F0(xy) = x + y
y\x 0 1 2 3 4 5
0 0 1 2 3 4 5
1 1 2 3 4 5 6
2 2 3 4 5 6 7
3 3 4 5 6 7 8
4 4 5 6 7 8 9
5 5 6 7 8 9 10
6 6 7 8 9 10 11
Valeurs de F1(xy)
y\x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29
2 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60
3 11 19 27 35 43 51 59 67 75 83 91 99 107 115 123
4 26 42 58 74 90 106 122 138 154 170 186 202 218 234 250
5 57 89 121 153 185 217 249 281 313 345 377 409 441 473 505
6 120 184 248 312 376 440 504 568 632 696 760 824 888 952 1016
7 247 375 503 631 759 887 1015 1143 1271 1399 1527 1655 1783 1911 2039
8 502 758 1014 1270 1526 1782 2038 2294 2550 2806 3062 3318 3574 3830 4086
9 1013 1525 2037 2549 3061 3573 4085 4597 5109 5621 6133 6645 7157 7669 8181
10 2036 3060 4084 5108 6132 7156 8180 9204 10228 11252 12276 13300 14324 15348 16372
11 4083 6131 8179 10227 12275 14323 16371 18419 20467 22515 24563 26611 28659 30707 32755
12 8178 12274 16370 20466 24562 28658 32754 36850 40946 45042 49138 53234 57330 61426 65522
13 16369 24561 32753 40945 49137 57329 65521 73713 81905 90097 98289 106481 114673 122865 131057
14 32752 49136 65520 81904 98288 114672 131056 147440 163824 180208 196592 212976 229360 245744 262128

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

Valeurs de F2(xy)
y\x 0 1 2 3 4 5
0 0 1 2 3 4 5
1 1 8 27 74 185 440
2 19 F1(8, 10) = 10 228 F1(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[modifier | modifier le code]

Article connexe[modifier | modifier le code]

Algorithme récursif

Liens externes[modifier | modifier le code]

Suites OEISA260003 et OEISA260004 de l'OEIS

Crédit d'auteurs[modifier | modifier le code]

(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).