Función de Sudán

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

La función de Sudán puede definirse de la siguiente manera:

Tabla de valores

Valores de F0

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

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
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)

Valores de F3
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.

Notas y referencias
  1. Ackermann, 1928.
  2. Calude, Marcus y Tevy, 1979.
  3. Sudan, 1927.

Bibliografía
  • 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. Parámetro desconocido |doi-access= ignorado (ayuda)
  • 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 ».

Enlaces externos
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.