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.La función de Sudán fue la primera función con dicha propiedad en ser publicada.

Fue descubierta y publicada en 1927 por Gabriel Sudán, 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 \ x0123456789100012345678910112345678910112234567891011123345678910111213445678910111213145567891011121314156678910111213141516778910111213141516178891011121314151617189910111213141516171819101011121314151617181920

Valores de F1

y \ x0123456789100012345678910113579111315171921248121620242832364044311192735435159677583914264258749010612213815417018655789121153185217249281313345377612018424831237644050456863269676072473755036317598871015114312711399152785027581014127015261782203822942550280630629101315252037254930613573408545975109562161331020363060408451086132715681809204102281125212276

Valores de F2 y \ x01234567001234567x1F1 (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)182774185440101522942x+1 · (x + 2) − x − 3≈ 10lg 2·(x+1) + lg(x+2)2F1 (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)191022815569256417≈ 5,742397643 · 1024≈ 3,668181327 · 1058≈ 5,019729940 · 10135≈ 1,428323374 · 10309≈ 3,356154368 · 1069422x+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)3F1 (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·10694expresión más larga, comienza con 222x+1 , ≈ 101010lg 2·(x+1) + lg(x+2)4F1 (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 · 1026514839expresió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

Bibliografía

Enlaces externos

OEIS: A260003, A260004

Categoría:Funciones especiales Categoría:Aritmética