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 ${\displaystyle x,y,n\in \mathbb {N} _{0}}$ gilt:

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

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

${\displaystyle 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₁(x, y)

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

Werte von 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 · 10^10	F1(74, 76) ≈ 5,74 · 10^24	F1(185, 187)	F1(440, 442)

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