Fonction de Sudan
fonction récursive mais non récursive primitive (calculabilité)
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- ,
- ,
- .
Tableaux de valeurs
modifier| 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 |
| 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(x, y) = F1(0, y) + 2y x.
| 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
modifierArticle connexe
modifierLiens externes
modifierCrédit d'auteurs
modifier(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).