Funció de Sudan

En la teoria de la computació, la funció de Sudan és un eixemple d'una funció recursiva que no és recursiva primitiva, la mateixa categoria a la qual pertany la més coneguda funció de Ackermann.La funció de Sudan va ser la primera funció en dita propietat en ser publicada.

Va ser descoberta i publicada en 1927 per Gabriel Sudan, un matemàtic rumà que va ser alumne del matemàtic David Hilbert.

Definició

La funció de Sudan pot definir-se de la següent manera:

$\begin{array}{cc}{F}_0(x,y)& =x+y\\ F_{n+1}(x,0)& =x& \text{if }n\ge 0\\ F_{n+1}(x,y+1)& =F_n(F_{n+1}(x,y),F_{n+1}(x,y)+y+1)& \text{if }n\ge 0\end{array}$

Taula de valors

Valores de F₀

$F_0(x,y)=x+y$

i  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

Valors de F₁

$F_1(x,y)=2y\cdot (x+2)-y-2$

i  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

Valors de F₂

i  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
	expressió més llarga, comença en 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
	expressió molt més llarga, comença en 2222x+1 ≈ 10101010lg 2·(x+1) + lg(x+2)

Valors de F₃

i  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 és possible usar expressions tancades usant notació 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 és possible usar expressions tancades usant notació matemàtica normal.

Bibliografia

• Ackermann, Wilhelm (1928). “Zoom Hilbertschen Aufbau der reellen Zahlen”. Mathematische Annalen 99: 118–133. doi:10.1007/BF01459088.

• “The first example of a recursive function which is not primitive recursive” (1979). Història Mathematica 6 (4): 380–384. doi:10.1016/0315-0860(79)90024-7.

• Suen, Gabriel (1927). “Sur li nomene transfini ω^ω”. Bulletin mathématique de la Société Roumaine dones Sciences 30: 11–30. “Jbuch 53, 171”