FANDOM


Die Ackermannfunktion ist eine 1928 von Wilhelm Ackermann veröffentlichte[1] Funktion, die berechenbar, jedoch nicht primitiv-rekursiv ist, und somit Gegenbeispiel für die Behauptung, jede berechenbare Funktion sei primitiv-rekursiv. Weniger bekannt ist die 1927 veröffentlichte Sudanfunktion, die ebenfalls diese Eigenschaft aufweist.

David Hilbert berichtete von Ackermanns Ergebnis bereits 1926.[2] In der Schrift heißt es in einer Fußnote: „Vortrag, gehalten am 4. Juni 1925 […].“ Unter der Voraussetzung, dass die Stelle über Ackermann nicht nachträglich ergänzt wurde, hatte Hilbert das Ergebnis also bereits 1925. Ackermann selbst bezieht sich in seiner Arbeit auf Sudan: „Eine Arbeit, die mit der vorliegenden manche Berührungspunkte hat, wird von Herrn G. Sudan publiziert werden. Es handelt sich bei ihr um die Definition von Zahlen der zweiten Zahlklasse, die man in ähnlicher Weise klassifizieren kann wie die Definitionen der reellen Zahlen.“ Hilbert war mit Ackermann und Sudan von 1922 bis 1925 in Deutschland. Das erste Beispiel einer berechenbaren Funktion, die nicht primitiv-rekursiv ist, wird daher sowohl Sudan als auch Ackermann zugeschrieben.[3]

Es gibt verschiedene Varianten, die ebenfalls Ackermannfunktion genannt werden.

Ursprüngliche Definition Bearbeiten

ϱc(f(c), a, n) ist die n-malige Iteration der Funktion f für das Argument a. Der Index c von ϱ weist darauf hin, dass ϱ von f statt c abhängt.

\varrho_c(f(c),a,0)=a
\varrho_c(f(c),a,n+1)=f(\varrho_c(f(c),a,n))

Die Nachfolgerfunktion (a + 1) wird als bekannt vorausgesetzt. Die Addition und Multiplikation werden rekursiv definiert:

a+0=a
a+(b+1)=(a+b)+1
a\cdot0=0
a\cdot(b+1)=a\cdot b+a

In der Arbeit steht fälschlicherweise „a · 0 = a“.

\lambda(a,b)=\begin{cases}1&a=b\\0&a\neq b\end{cases}\qquad\iota(a,b)=\begin{cases}0&a=b\\1&a\neq b\end{cases}
\alpha(a,n)=\iota(n,1)\cdot\iota(n,0)\cdot a+\lambda(n,1)

Es gilt also:

\alpha(a,n)=\begin{cases}0&n=0\\1&n=1\\a&\text{sonst}\end{cases}

Die Ackermannfunktion φ wird schließlich gegeben durch:

\varphi(a,b,0)=a+b
\varphi(a,b,n+1)=\varrho_c(\varphi(a,c,n),\alpha(a,n),b)

Es gilt:

\varphi(a,b,0)=a+b
\varphi(a,0,n+1)=\alpha(a,n)
\varphi(a,b+1,n+1)=\varphi(a,\varphi(a,b,n+1),n)

Diese Funktion ist mit den Hyperoperationen verwandt:

a^{(n)}b=\begin{cases}\varphi(a,b,n-1)&1\leq n\leq3\\\varphi(a,b-1,n-1)&n\geq4\end{cases}

Eine Variante ist A mit A(a, b, n) = a(n + 1)b. Hilbert (1926) erwähnte die Funktion als φ mit φn(a, b) = a(n)b.

Variante von Péter Bearbeiten

Rózsa Péter definierte 1935 eine Variante mit nur zwei Parametern.[4]

\varphi_0(n)=2n+1
\varphi_{m+1}(0)=\varphi_m(1)
\varphi_{m+1}(n+1)=\varphi_m(\varphi_{m+1}(n))

Variante von Robinson Bearbeiten

Raphael M. Robinson vereinfachte Péters Variante 1948.[5] Sei Sx der Nachfolger von x.

\operatorname G_0x=\operatorname Sx,\quad\operatorname G_{\operatorname Sn}0=\operatorname G_n1,\quad\operatorname G_{\operatorname Sn}\operatorname Sx=\operatorname G_n\operatorname G_{\operatorname Sn}x

Es ist Gnx = 2(n)(x + 3) − 3.

Einzelnachweise Bearbeiten

  1. Wilhelm Ackermann: Zum Hilbertschen Aufbau der reellen Zahlen. In: Mathematische Annalen. Band 99, 1928, S. 118–133, doi:10.1007/BF01459088 (online).
  2. David Hilbert: Über das Unendliche. In: Mathematische Annalen. Band 95, 1926, S. 161–190, doi:10.1007/BF01206605 (online).
  3. Cristian Calude, Solomon Marcus, Ionel Tevy: The First Example of a Recursive Function Which Is Not Primitive Recursive. In: Historia Mathematica. Band 6, Nr. 4, November 1979, S. 380–384, doi:10.1016/0315-0860(79)90024-7.
  4. Rózsa Péter: Konstruktion nichtrekursiver Funktionen. In: Mathematische Annalen. Band 111, 1935, S. 42–60, doi:10.1007/BF01472200 (online).
  5. Raphael M. Robinson: Recursion and Double Recursion. In: Bulletin of the American Mathematical Society. Band 54, Nr. 10, 1948, S. 987–993, doi:10.1090/S0002-9904-1948-09121-2 (online).

Störung durch Adblocker erkannt!


Wikia ist eine gebührenfreie Seite, die sich durch Werbung finanziert. Benutzer, die Adblocker einsetzen, haben eine modifizierte Ansicht der Seite.

Wikia ist nicht verfügbar, wenn du weitere Modifikationen in dem Adblocker-Programm gemacht hast. Wenn du sie entfernst, dann wird die Seite ohne Probleme geladen.

Auch bei FANDOM

Zufälliges Wiki