Fonction de Sudan
# 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

    $F_{0}(x,y)=x+y$,
    $F_{n+1}(x,0)=x\quad (\forall n\in \mathbb {N} )$,
    $F_{n+1}(x,y+1)=F_{n}(F_{n+1}(x,y),F_{n+1}(x,y)+y+1)\quad (\forall n\in \mathbb {N} )$.

## Tableaux de valeurs

Valeurs de $F_0(x,$ y) = 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 $F_1(x,$ y) :

| 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 $F_1(x,$ y) = $F_1(0,$ y) + $2^y$ x.

Valeurs de $F_2(x,$ y) :

| y\x | 0 | 1 | 2 | 3 | 4 | 5 |
| - | - | - | - | - | - | - |
| 0 | 0 | 1 | 2 | 3 | 4 | 5 |
| 1 | 1 | 8 | 27 | 74 | 185 | 440 |
| 2 | 19 | $F_1(8,$ 10) = 10 228 | $F_1(27,$ 29) = 15 569 256 417 ≈ $1,55.10^{10}$ | $F_1(74,$ 76) ≈ $5,74.10^{24}$ | $F_1(185,$ 187) ≈ $3,67.10^{58}$ | $F_1(440,$ 442) ≈ $5,02.10^{135}$ |
