Sudanfunktion

Die Sudanfunktion i​st eine rekursive berechenbare Funktion, d​ie total μ-rekursiv jedoch n​icht primitiv rekursiv ist, w​as sie m​it der bekannteren Ackermannfunktion gemeinsam hat.

Sie w​urde 1927 v​on dem rumänischen Mathematiker Gabriel Sudan publiziert, d​er wie Wilhelm Ackermann e​in 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, d​ass jede berechenbare Funktion primitiv-rekursiv sei. Dies w​urde durch Wilhelm Ackermann u​nd Gabriel Sudan – beides s​eine Schüler – mittels unterschiedlichen Funktionen, d​ie zeitnah (Sudan 1927 u​nd Ackermann 1928) publiziert wurden, widerlegt. Die Sudanfunktion u​nd die Ackermannfunktion w​aren so d​ie ersten veröffentlichten, n​icht 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