Sudanfunktion

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.

Inhaltsverzeichnis

Definition

Für x, y, n \in \N_0 gilt:

F_0 (x, y) = x+y,\,
F_{n+1} (x, 0) = x, \ n \ge 0\,
F_{n+1} (x, y+1) = F _n (F_{n+1} (x, y), F_{n+1} (x, y) + y + 1), \ n\ge 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 F1(mn)
m\n 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 F2(mn)
m\n 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) F1(440, 442)

Literatur

  • Gabriel Sudan, Sur le nombre transfini ωω, Bulletin Math. Soc. Roumaine des sciences 30, 11–30 (1927). JFM review
  • Wilhelm Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen, Mathematische Annalen 99, 118–133 (1928). JFM review
  • Cristian Calude, Solomon Marcus, 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

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Primitive Rekursion — Primitiv rekursive Funktionen sind totale Funktionen, die aus einfachen Grundfunktionen (konstante 0 Funktion, Projektionen auf ein Argument und Nachfolgefunktion) durch Komposition und (primitive) Rekursion gebildet werden können. Der Begriff… …   Deutsch Wikipedia

  • My-Rekursion — Die Klasse Pr der μ rekursiven Funktionen oder partiell rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle. Sie beschreibt die Menge aller Funktionen, die im intuitiven Sinn… …   Deutsch Wikipedia

  • My-rekursive Funktion — Die Klasse Pr der μ rekursiven Funktionen oder partiell rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle. Sie beschreibt die Menge aller Funktionen, die im intuitiven Sinn… …   Deutsch Wikipedia

  • Partiell-rekursive Funktion — Die Klasse Pr der μ rekursiven Funktionen oder partiell rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle. Sie beschreibt die Menge aller Funktionen, die im intuitiven Sinn… …   Deutsch Wikipedia

  • Primitiv-rekursive Funktion — Primitiv rekursive Funktionen sind totale Funktionen, die aus einfachen Grundfunktionen (konstante 0 Funktion, Projektionen auf ein Argument und Nachfolgefunktion) durch Komposition und (primitive) Rekursion gebildet werden können. Der Begriff… …   Deutsch Wikipedia

  • Μ-Operator — Die Klasse Pr der μ rekursiven Funktionen oder partiell rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle. Sie beschreibt die Menge aller Funktionen, die im intuitiven Sinn… …   Deutsch Wikipedia

  • Μ-Rekursion — Die Klasse Pr der μ rekursiven Funktionen oder partiell rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle. Sie beschreibt die Menge aller Funktionen, die im intuitiven Sinn… …   Deutsch Wikipedia

  • Μ-rekursive Funktion — Die Klasse Pr der μ rekursiven Funktionen oder partiell rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle. Sie beschreibt die Menge aller Funktionen, die im intuitiven Sinn… …   Deutsch Wikipedia

  • μ-Rekursion — Die Klasse Pr der μ rekursiven Funktionen oder partiell rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle. Sie beschreibt die Menge aller Funktionen, die im intuitiven Sinn… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”