Funzione di Sudan

Nella teoria della calcolabilità, la funzione di Sudan è una funzione ricorsiva totale non primitiva.

La funzione era la prima che confutò la credenza che le funzioni ricorsive fossero necessariamente primitive. La scoperta è attribuita al matematico Gabriel Sudan, uno studente di David Hilbert nel 1927, qualche anno prima di quella della più nota funzione di Ackermann.

Definizione

Siano $n,x,y\in \mathbb {N}$

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

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

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

Tabella dei valori

Valori di 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

Valori di F₁(x, y)(OEIS:A260003)

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

Si ha: $F_{1}(x,y)=F_{1}(0,y)+2^{y}x$.

Valori di F₂(x, y)(OEIS:A260004)

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

• Cristian Calude, Solomon Marcus et Ionel Tevy, The first example of a recursive function which is not primitive recursive, Historia Mathematica 6, 1979, no. 4, 380–384 doi:10.1016/0315-0860(79)90024-7.
• Sudan function - Jump up Bull. Math. Soc. Roumaine Sci. 30, 1927, 11 - 30; Jbuch 53, 171.