Ackermannfunktion

Die Ackermannfunktion ist eine 1928 von Wilhelm Ackermann veröffentlichte 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. 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.

Es gibt verschiedene Varianten, die ebenfalls Ackermannfunktion genannt werden.

Ursprüngliche Definition

ϱ_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\cdot 0=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⁽ⁿ⁾b.

Variante von Péter

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

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

Raphael M. Robinson vereinfachte Péters Variante 1948. 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 G_nx = 2⁽ⁿ⁾(x + 3) − 3.