Función de Sudán
función matemática
(Redirigido desde «Función de Sudan»)
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.
Definición
editarLa función de Sudán puede definirse de la siguiente manera:
Tabla de valores
editarValores de F0
editar
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 |
Valores de F1
editar
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 |
Valores de F2
editary \ 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) |
Valores de F3
editary \ 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. |
Notas y referencias
editarBibliografía
editar- Ackermann, Wilhelm (1928). «Zum Hilbertschen Aufbau der reellen Zahlen». Mathematische Annalen 99: 118-133. JFM 54.0056.06. S2CID 123431274. doi:10.1007/BF01459088.
- Calude, Cristian; Marcus, Solomon; Tevy, Ionel (1979). «The first example of a recursive function which is not primitive recursive». Historia Mathematica 6 (4): 380-384. doi:10.1016/0315-0860(79)90024-7.
- Sudan, Gabriel (1927). «Sur le nombre transfini ωω». Bulletin mathématique de la Société Roumaine des Sciences 30: 11-30. JFM 53.0171.01. JSTOR 43769875. «Jbuch 53, 171».