title: Fonction de Sudan
text: # 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}$ |
  