Funció de Sudan

En la teoria de la computació, la funció de Sudan és un exemple d'una funció recursiva, però no primitiva recursiva. Això també és cert per la més coneguda funció d'Ackermann. La funció de Sudan va ser la primera funció que va publicar aquesta propietat.

Va ser descoberta (i publicada) el 1927 per Gabriel Sudan, un matemàtic romanès que era estudiant de David Hilbert.

Definició

$F_{0}(x,y)=x+y,$

$F_{n+1}(x,0)=x,\ n\geq 0$

$F_{n+1}(x,y+1)=F_{n}(F_{n+1}(x,y),F_{n+1}(x,y)+y+1),\ n\geq 0.$

Taules de valors

Valors de F₀(x, y)

y\x	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	2	3	4	5	6
2	2	3	4	5	6	7
3	3	4	5	6	7	8
4	4	5	6	7	8	9
5	5	6	7	8	9	10
6	6	7	8	9	10	11

Valors de F₁(x, y)

y\x	0	1	2	3	4	5	6
0	0	1	2	3	4	5	6
1	1	3	5	7	9	11	13
2	4	8	12	16	20	24	28
3	11	19	27	35	43	51	59
4	26	42	58	74	90	106	122
5	57	89	121	153	185	217	249
6	120	184	248	312	376	440	504

En general, F₁(x, y) és igual a F₁(0, y) + 2^y x.

Valors de F₂(x, y)

y\x	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	8	27	74	185	440
2	19	F1(8, 10) = 10228	F1(27, 29) ≈ 1.55 ×1010	F1(74, 76) ≈ 5.74 ×1024	F1(185, 187) ≈ 3.67 ×1058	F1(440, 442) ≈ 5.02 ×10135

Bibliografia

• Calude, Cristian; Marcus, Solomon; Tevy, Ionel «The first example of a recursive function which is not primitive recursive» (en anglès). Historia Mathematica 6 (1979), no. 4, 380-384. DOI: 10.1016/0315-0860(79)90024-7.

Enllaços externs

• OEIS: A260003, A260004