Worldlex Wiki En théorie du calcul , la fonction Sudan est un exemple de fonction récursive , mais non récursive primitive . C'est également le cas de la fonction d'Ackermann, plus connue .
En 1926, David Hilbert conjectura que toute fonction calculable était primitive récursive. Cette conjecture fut réfutée par Gabriel Sudan et Wilhelm Ackermann
Calcul
Ces équations peuvent être utilisées comme règles d'un système de réécriture de termes (TRS) .
La fonction généralisée conduit aux règles de réécriture
À chaque étape de réduction, l'occurrence la plus à droite et la plus intérieure de F est réécrite, par application de l'une des règles (r1) - (r3).
Calude (1988) donne un exemple : calculer .
La séquence de réduction est
Tableaux de valeurs
Valeurs de F 0
F 0 ( x , y ) = x + y
| y \ x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 2 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 3 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 4 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 5 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 6 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 7 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| 8 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| 9 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| 10 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
Valeurs de F 1
F 1 ( X , y ) = 2 y · (x + 2) − y − 2
| y \ x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 |
| 2 | 4 | 8 | 12 | 16 | 20 | 24 | 28 | 32 | 36 | 40 | 44 |
| 3 | 11 | 19 | 27 | 35 | 43 | 51 | 59 | 67 | 75 | 83 | 91 |
| 4 | 26 | 42 | 58 | 74 | 90 | 106 | 122 | 138 | 154 | 170 | 186 |
| 5 | 57 | 89 | 121 | 153 | 185 | 217 | 249 | 281 | 313 | 345 | 377 |
| 6 | 120 | 184 | 248 | 312 | 376 | 440 | 504 | 568 | 632 | 696 | 760 |
| 7 | 247 | 375 | 503 | 631 | 759 | 887 | 1015 | 1143 | 1271 | 1399 | 1527 |
| 8 | 502 | 758 | 1014 | 1270 | 1526 | 1782 | 2038 | 2294 | 2550 | 2806 | 3062 |
| 9 | 1013 | 1525 | 2037 | 2549 | 3061 | 3573 | 4085 | 4597 | 5109 | 5621 | 6133 |
| 10 | 2036 | 3060 | 4084 | 5108 | 6132 | 7156 | 8180 | 9204 | 10228 | 11252 | 12276 |
Valeurs de F 2
| y \ x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| x | ||||||||
| 1 | F 1 (F 2 (0, 0), F 2 (0, 0)+1) | F 1 (F 2 (1, 0), F 2 (1, 0)+1) | F 1 (F 2 (2, 0), F 2 (2, 0)+1) | F 1 (F 2 (3, 0), F 2 (3, 0)+1) | F 1 (F 2 (4, 0), F 2 (4, 0)+1) | F 1 (F 2 (5, 0), F 2 (5, 0)+1) | F 1 (F 2 (6, 0), F 2 (6, 0)+1) | F 1 (F 2 (7, 0), F 2 (7, 0)+1) |
| F 1 (0, 1) | F 1 (1, 2) | F 1 (2, 3) | F 1 (3, 4) | F 1 (4, 5) | F 1 (5, 6) | F 1 (6, 7) | F 1 (7, 8) | |
| 1 | 8 | 27 | 74 | 185 | 440 | 1015 | 2294 | |
| 2 x+1 · (x + 2) − x − 3 ≈ 10 lg 2·(x+1) + lg(x+2) | ||||||||
| 2 | F 1 (F 2 (0, 1), F 2 (0, 1)+2) | F 1 (F 2 (1, 1), F 2 (1, 1)+2) | F 1 (F 2 (2, 1), F 2 (2, 1)+2) | F 1 (F 2 (3, 1), F 2 (3, 1)+2) | F 1 (F 2 (4, 1), F 2 (4, 1)+2) | F 1 (F 2 (5, 1), F 2 (5, 1)+2) | F 1 (F 2 (6, 1), F 2 (6, 1)+2) | F 1 (F 2 (7, 1), F 2 (7, 1)+2) |
| F 1 (1, 3) | F 1 (8, 10) | F 1 (27, 29) | F 1 (74, 76) | F 1 (185, 187) | F 1 (440, 442) | F 1 (1015, 1017) | F 1 (2294, 2296) | |
| 19 | 10228 | 15569256417 | ≈ 5 742 397 643 · 10²⁴ | ≈ 3,668181327 · 10 58 | ≈ 5 019 729 940 · 10 135 | ≈ 1 428 323 374 · 10 309 | ≈ 3,356154368 · 10 694 | |
| 2 2 x+1 ·(x+2) − x − 1 · (2 x+1 ·(x+2) − x − 1) − (2 x+1 ·(x+2) − x + 1) ≈ 10 lg 2 · (2 x+1 ·(x+2) − x − 1) + lg(2 x+1 ·(x+2) − x − 1) ≈ 10 lg 2 · 2 x+1 ·(x+2) + lg(2 x+1 ·(x+2)) ≈ 10 lg 2 · (2 x+1 ·(x+2)) = 10 10 lg lg 2 + lg 2·(x+1) + lg(x+2) ≈ 10 10 lg 2·(x+1) + lg(x+2) | ||||||||
| 3 | F 1 (F 2 (0, 2), F 2 (0, 2)+3) | F 1 (F 2 (1, 2), F 2 (1, 2)+3) | F 1 (F 2 (2, 2), F 2 (2, 2)+3) | F 1 (F 2 (3, 2), F 2 (3, 2)+3) | F 1 (F 2 (4, 2), F 2 (4, 2)+3) | F 1 (F 2 (5, 2), F 2 (5, 2)+3) | F 1 (F 2 (6, 2), F 2 (6, 2)+3) | F 1 (F 2 (7, 2), F 2 (7, 2)+3) |
| F 1 (F 1 (1,3), F 1 (1,3)+3) | F 1 (F 1 (8,10), F 1 (8,10)+3) | F 1 (F 1 (27,29), F 1 (27,29)+3) | F 1 (F 1 (74,76), F 1 (74,76)+3) | F 1 (F 1 (185,187), F 1 (185,187)+3) | F 1 (F 1 (440,442), F 1 (440,442)+3) | F 1 (F 1 (1015,1017), F 1 (1015,1017)+3) | F 1 (F 1 (2294,2297), F 1 (2294,2297)+3) | |
| F 1 (19, 22) | F 1 (10228, 10231) | F 1 (15569256417, 15569256420) | F 1 (≈6·10 24 , ≈6·10 24 ) | F 1 (≈4·10 58 , ≈4·10 58 ) | F 1 (≈5·10 135 , ≈5·10 135 ) | F 1 (≈10 309 , ≈10 309 ) | F 1 (≈3·10 694 , ≈3·10 694 ) | |
| 88080360 | ≈ 7,04 · 10 3083 | ≈ 7,82 · 10 4686813201 | ≈ 10 1,72·10 24 | ≈ 10 1,10·10 58 | ≈ 10 1,51·10 135 | ≈ 10 4,30·10 308 | ≈ 10 1,01·10 694 | |
| expression plus longue, commence par 2 2 2 x+1 an, ≈ 10 10 10 lg 2·(x+1) + lg(x+2) | ||||||||
| 4 | F 1 (F 2 (0, 3), F 2 (0, 3)+4) | F 1 (F 2 (1, 3), F 2 (1, 3)+4) | F 1 (F 2 (2, 3), F 2 (2, 3)+4) | F 1 (F 2 (3, 3), F 2 (3, 3)+4) | F 1 (F 2 (4, 3), F 2 (4, 3)+4) | F 1 (F 2 (5, 3), F 2 (5, 3)+4) | F 1 (F 2 (6, 3), F 2 (6, 3)+4) | F 1 (F 2 (7, 3), F 2 (7, 3)+4) |
| F 1 (F 1 (19, 22), F 1 (19, 22)+4) | F 1 (F 1 (10228, 10231), F 1 (10228, 10231)+4) | F 1 (F 1 (15569256417, 15569256420), F 1 (15569256417, 15569256420)+4) | F 1 (F 1 (≈5,74·10 24 , ≈5,74·10 24 ), F 1 (≈5,74·10 24 , ≈5,74·10 24 )) | F 1 (F 1 (≈3,67·10 58 , ≈3,67·10 58 ), F 1 (≈3,67·10 58 , ≈3,67·10 58 )) | F 1 (F 1 (≈5,02·10 135 , ≈5,02·10 135 ), F 1 (≈5,02·10 135 , ≈5,02·10 135 )) | F 1 (F 1 (≈1,43·10 309 , ≈1,43·10 309 ), F 1 (≈1,43·10 309 , ≈1,43·10 309 )) | F 1 (F 1 (≈3,36·10 694 , ≈3,36·10 694 ), F 1 (≈3,36·10 694 , ≈3,36·10 694 )) | |
| F 1 (88080360, 88080364) | F 1 (10230·2 10231 −10233, 10230·2 10231 −10229) | |||||||
| ≈ 3,5 · 10 26514839 | ||||||||
| expression beaucoup plus longue, commence par 2 2 2 2 x+1 an, ≈ 10 10 10 10 lg 2·(x+1) + lg(x+2) | ||||||||
Valeurs de F 3
| y \ x | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 |
| x | |||||
| 1 | F 2 (F 3 (0, 0), F 3 (0, 0)+1) | F 2 (F 3 (1, 0), F 3 (1, 0)+1) | F 2 (F 3 (2, 0), F 3 (2, 0)+1) | F 2 (F 3 (3, 0), F 3 (3, 0)+1) | F 2 (F 3 (4, 0), F 3 (4, 0)+1) |
| F 2 (0, 1) | F 2 (1, 2) | F 2 (2, 3) | F 2 (3, 4) | F 2 (4, 5) | |
| 1 | 10228 | ≈ 7,82 · 10 4686813201 | |||
| Aucune expression fermée n'est possible dans le cadre de la notation mathématique normale. | |||||
| 2 | F 3 (F 4 (0, 1), F 4 (0, 1)+2) | F 3 (F 4 (1, 1), F 4 (1, 1)+2) | F 3 (F 4 (2, 1), F 4 (2, 1)+2) | F 3 (F 4 (3, 1), F 4 (3, 1)+2) | F 3 (F 4 (4, 1), F 4 (4, 1)+2) |
| F 3 (1, 3) | F 3 (10228, 10230) | F 3 (≈10 4686813201 , ≈10 4686813201 ) | |||
| Aucune expression fermée n'est possible dans le cadre de la notation mathématique normale. | |||||