Sudanfunktion

Die Sudanfunktion ist eine rekursive berechenbare Funktion, die total μ-rekursiv, jedoch nicht primitiv rekursiv ist, was sie mit der bekannteren Ackermannfunktion gemeinsam hat.

Sie wurde 1927 von dem rumänischen Mathematiker Gabriel Sudan publiziert, der wie Wilhelm Ackermann ein Schüler David Hilberts war.

Definition

Für $x,y,n\in \mathbb {N} _{0}$ gilt:

$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.\,$

Hintergrund

1926 vermutete David Hilbert, dass jede berechenbare Funktion primitiv-rekursiv sei. Dies wurde durch Wilhelm Ackermann und Gabriel Sudan – beides seine Schüler – mittels unterschiedlichen Funktionen, die zeitnah (Sudan 1927 und Ackermann 1928) publiziert wurden, widerlegt. Die Sudanfunktion und die Ackermannfunktion waren so die ersten veröffentlichten, nicht primitiv rekursiven Funktionen.

Wertetabellen

Werte von F₀

F₀ lässt sich geschlossen darstellen als:  F₀(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

Werte von F₁

F₁ lässt sich geschlossen darstellen als:  F₁(x, y) = 2^y · (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

Werte von F₂

F₂ lässt sich nicht mehr allgemein geschlossen darstellen.

Für gegebene y lässt es sich geschlossen darstellen, wobei die Ausdrücke schnell längere Ausdrücke werden.

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	2284
	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
	längerer Ausdruck, fängt mit 222x+1 an,  ≈ 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
	noch längerer Ausdruck, fängt mit 2222x+1 an,  ≈ 10101010lg 2·(x+1) + lg(x+2)

Werte von F₃

F₃ lässt sich nicht mehr geschlossen darstellen.

y \ x	0	1	2	3	4
0	0	1	2	3	4
	x
1	F2 (F3(0, 0),   F3(0, 0)+1)	F2 (F3(1, 0),   F3(1, 0)+1)	F2 (F3(2, 0),   F3(2, 0)+1)	F2 (F3(3, 0),   F3(3, 0)+1)	F2 (F3(4, 0),   F3(4, 0)+1)
	F2(0, 1)	F2(1, 2)	F2(2, 3)	F2(3, 4)	F2(4, 5)
	1	10228	≈ 7,82 · 104686813201
	keine geschlossenen Ausdrücke im Rahmen normaler mathematischer Notation möglich
2	F3 (F4(0, 1),   F4(0, 1)+2)	F3 (F4(1, 1),   F4(1, 1)+2)	F3 (F4(2, 1),   F4(2, 1)+2)	F3 (F4(3, 1),   F4(3, 1)+2)	F3 (F4(4, 1),   F4(4, 1)+2)
	F3 (1, 3)	F3 (10228, 10230)	F3 (≈104686813201,  ≈104686813201)
	keine geschlossenen Ausdrücke im Rahmen normaler mathematischer Notation möglich

Literatur

• Gabriel Sudan: Sur le nombre transfini ω^ω. Bulletin Math. Soc. Roumaine des sciences 30, S. 11–30 (1927). JFM review
• Wilhelm Ackermann: Zum Hilbertschen Aufbau der reellen Zahlen. Mathematische Annalen 99, S. 118–133 (1928). JFM review
• Cristian S. Calude, Solomon Marcus, Ionel Tevy: The first example of a recursive function which is not primitive recursive. Historia Mathematica 6 (1979), no. 4, S. 380–384 doi:10.1016/0315-0860(79)90024-7