Loading AI tools
función matemática De Wikipedia, la enciclopedia libre
En la teoría de la computación, la función de Sudán es un ejemplo de una función recursiva que no es recursiva primitiva, la misma categoría a la cual pertenece la más conocida función de Ackermann.[1]La función de Sudán fue la primera función con dicha propiedad en ser publicada.[2]
Fue descubierta y publicada en 1927 por Gabriel Sudán,[3] un matemático rumano que fue alumno del matemático David Hilbert.
La función de Sudán puede definirse de la siguiente manera:
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 |
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 |
y \ x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
x | ||||||||
1 | F1 (F2(0, 0), F2(0, 0)+1) |
F1 (F2(1, 0), F2(1, 0)+1) |
F1 (F2(2, 0), F2(2, 0)+1) |
F1 (F2(3, 0), F2(3, 0)+1) |
F1 (F2(4, 0), F2(4, 0)+1) |
F1 (F2(5, 0), F2(5, 0)+1) |
F1 (F2(6, 0), F2(6, 0)+1) |
F1 (F2(7, 0), F2(7, 0)+1) |
F1(0, 1) | F1(1, 2) | F1(2, 3) | F1(3, 4) | F1(4, 5) | F1(5, 6) | F1(6, 7) | F1(7, 8) | |
1 | 8 | 27 | 74 | 185 | 440 | 1015 | 2294 | |
2x+1 · (x + 2) − x − 3 ≈ 10lg 2·(x+1) + lg(x+2) | ||||||||
2 | F1 (F2(0, 1), F2(0, 1)+2) |
F1 (F2(1, 1), F2(1, 1)+2) |
F1 (F2(2, 1), F2(2, 1)+2) |
F1 (F2(3, 1), F2(3, 1)+2) |
F1 (F2(4, 1), F2(4, 1)+2) |
F1 (F2(5, 1), F2(5, 1)+2) |
F1 (F2(6, 1), F2(6, 1)+2) |
F1 (F2(7, 1), F2(7, 1)+2) |
F1(1, 3) | F1(8, 10) | F1(27, 29) | F1(74, 76) | F1(185, 187) | F1(440, 442) | F1(1015, 1017) | F1(2294, 2296) | |
19 | 10228 | 15569256417 | ≈ 5,742397643 · 1024 | ≈ 3,668181327 · 1058 | ≈ 5,019729940 · 10135 | ≈ 1,428323374 · 10309 | ≈ 3,356154368 · 10694 | |
22x+1·(x+2) − x − 1 · (2x+1·(x+2) − x − 1) − (2x+1·(x+2) − x + 1) ≈ 10lg 2 · (2x+1·(x+2) − x − 1) + lg(2x+1·(x+2) − x − 1) ≈ 10lg 2 · 2x+1·(x+2) + lg(2x+1·(x+2)) ≈ 10lg 2 · (2x+1·(x+2)) = 1010lg lg 2 + lg 2·(x+1) + lg(x+2) ≈ 1010lg 2·(x+1) + lg(x+2) | ||||||||
3 | F1 (F2(0, 2), F2(0, 2)+3) |
F1 (F2(1, 2), F2(1, 2)+3) |
F1 (F2(2, 2), F2(2, 2)+3) |
F1 (F2(3, 2), F2(3, 2)+3) |
F1 (F2(4, 2), F2(4, 2)+3) |
F1 (F2(5, 2), F2(5, 2)+3) |
F1 (F2(6, 2), F2(6, 2)+3) |
F1 (F2(7, 2), F2(7, 2)+3) |
F1(F1(1,3), F1(1,3)+3) |
F1(F1(8,10), F1(8,10)+3) |
F1(F1(27,29), F1(27,29)+3) |
F1(F1(74,76), F1(74,76)+3) |
F1(F1(185,187), F1(185,187)+3) |
F1(F1(440,442), F1(440,442)+3) |
F1(F1(1015,1017), F1(1015,1017)+3) |
F1(F1(2294,2297), F1(2294,2297)+3) | |
F1(19, 22) | F1(10228, 10231) | F1(15569256417, 15569256420) |
F1(≈6·1024, ≈6·1024) | F1(≈4·1058, ≈4·1058) | F1(≈5·10135, ≈5·10135) | F1(≈10309, ≈10309) | F1(≈3·10694, ≈3·10694) | |
88080360 | ≈ 7,04 · 103083 | ≈ 7,82 · 104686813201 | ≈ 101,72·1024 | ≈ 101,10·1058 | ≈ 101,51·10135 | ≈ 104,30·10308 | ≈ 101,01·10694 | |
expresión más larga, comienza con 222x+1 , ≈ 101010lg 2·(x+1) + lg(x+2) | ||||||||
4 | F1 (F2(0, 3), F2(0, 3)+4) |
F1 (F2(1, 3), F2(1, 3)+4) |
F1 (F2(2, 3), F2(2, 3)+4) |
F1 (F2(3, 3), F2(3, 3)+4) |
F1 (F2(4, 3), F2(4, 3)+4) |
F1 (F2(5, 3), F2(5, 3)+4) |
F1 (F2(6, 3), F2(6, 3)+4) |
F1 (F2(7, 3), F2(7, 3)+4) |
F1 (F1(19, 22), F1(19, 22)+4) |
F1 (F1(10228, 10231), F1(10228, 10231)+4) |
F1 (F1(15569256417, 15569256420), F1(15569256417, 15569256420)+4) |
F1 (F1(≈5,74·1024, ≈5,74·1024), F1(≈5,74·1024, ≈5,74·1024)) |
F1 (F1(≈3,67·1058, ≈3,67·1058), F1(≈3,67·1058, ≈3,67·1058)) |
F1 (F1(≈5,02·10135, ≈5,02·10135), F1(≈5,02·10135, ≈5,02·10135)) |
F1 (F1(≈1,43·10309, ≈1,43·10309), F1(≈1,43·10309, ≈1,43·10309)) |
F1 (F1(≈3,36·10694, ≈3,36·10694), F1(≈3,36·10694, ≈3,36·10694)) | |
F1(88080360, 88080364) |
F1(10230·210231−10233, 10230·210231−10229) |
|||||||
≈ 3,5 · 1026514839 | ||||||||
expresión mucho más larga, comienza con 2222x+1 ≈ 10101010lg 2·(x+1) + lg(x+2) |
y \ X | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
0 | 0 | 1 | 2 | 3 | 4 |
X | |||||
1 | F 2 (F 3 (0, 0), </br>F 3 (0, 0)+1) |
F 2 (F 3 (1, 0), </br>F 3 (1, 0)+1) |
F 2 (F 3 (2, 0), </br>F 3 (2, 0)+1) |
F 2 (F 3 (3, 0), </br>F 3 (3, 0)+1) |
F 2 (F 3 (4, 0), </br>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 | |||
No es posible usar expresiones cerradas usando notación matemática normal. | |||||
2 | F 3 (F 4 (0, 1), </br>F 4 (0, 1)+2) |
F 3 (F 4 (1, 1), </br>F 4 (1, 1)+2) |
F 3 (F 4 (2, 1), </br>F 4 (2, 1)+2) |
F 3 (F 4 (3, 1), </br>F 4 (3, 1)+2) |
F 3 (F 4 (4, 1), </br>F 4 (4, 1)+2) |
F 3 (1, 3) | F 3 (10228, 10230) | F 3 (≈10 4686813201 , </br>≈10 4686813201 ) |
|||
No es posible usar expresiones cerradas usando notación matemática normal. |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.