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.​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:

${\begin{array}{lll}F_{0}(x,y)&=x+y\\F_{n+1}(x,0)&=x&{\text{if }}n\geq 0\\F_{n+1}(x,y+1)&=F_{n}(F_{n+1}(x,y),F_{n+1}(x,y)+y+1)&{\text{if }}n\geq 0\\\end{array}}$

Tabla de valores

Valores de F₀

$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

Valores de F₁

$F_{1}(x,y)=2y\cdot (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

Valores de F₂

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 F₃

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.

Bibliografía

• 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». 

Enlaces externos

• OEIS: A260003, A260004

• Datos: Q118107