Ackermannfunktion

Die Ackermannfunktion, 1928 von dem Mathematiker Wilhelm Ackermann definiert, spielt auf Grund ihres starken Wachstums in der Berechenbarkeitstheorie eine wichtige Rolle. Sie ist berechenbar, aber nicht primitiv-rekursiv, denn sie wächst schneller als jede primitiv-rekursive Funktion.

Definition

Heute ist die folgende, von Hans Hermes vereinfachte Version $ack$ gebräuchlich:

$ack\left(0,y\right):=y+1$
$ack\left(x,0\right):=ack\left(x-1,1\right)$
$ack\left(x,y\right):=ack\left(x-1,ack\left(x,y-1\right)\right)$

Beispiele:

$ack\left(2,0\right)=ack\left(1,1\right)=ack\left(0,ack\left(1,0\right)\right)=ack\left(0,ack\left(0,1\right)\right)=ack\left(0,2\right)=3$
$ack\left(1,2\right)=ack\left(0,ack\left(1,1\right)\right)=ack\left(0,3\right)=4$
$ack\left(2,1\right)=ack\left(1,ack\left(2,0\right)\right)=ack\left(1,3\right)=ack\left(0,ack\left(1,2\right)\right)=ack\left(0,4\right)=5$

Es gibt noch eine weiter vereinfachte Variante $a$ :

$a\left(0,y\right):=a\left(x,0\right):=1$
$a\left(1,y\right):=3y+1$
$a\left(x,y\right):=a\left(x-1,a\left(x-1,\ldots a\left(x-1,y\right)\ldots \right)\right)$ (y mal)

Implementation

In der Programmiersprache C lässt sich die Ackermannfunktion wie folgt implementieren:

int ack(int x, int y)
{
  if (y == 0)
   return x + 1;
  else if (x == 0)
   return ack(x - 1, 1);
  else
   return ack(x - 1, ack(x, y - 1));
}

Rekursiv, aber nicht primitiv-rekursiv

Die Ackermannfunktion wächst extrem schnell; schon $ack(4,2)$ ist ungefähr $2\cdot 10^{19728}$ . Dieses starke Wachstum wird ausgenutzt, um zu beweisen, dass die (z.B. WHILE-) berechenbare Funktion $f(n):=ack(n,n)$ schneller wächst als jede primitiv-rekursive Funktion und deshalb selbst nicht primitiv-rekursiv ist, damit auch nicht LOOP-berechenbar. Das heißt, dass man sie nicht in der einfachen Programmiersprache LOOP aufschreiben kann, in der nur Addition, Wertzuweisungen und endlich oft durchlaufene Schleife (Programmierung)n möglich sind.

Da die Ackermannfunktion WHILE-berechenbar ist, ist sie auch µ-rekursiv. Es ist jedoch nicht einfach, eine explizite µ-rekursive Definition anzugeben.

Wertetabelle

Werte von $ack(x,y)$
x\y	0	1	2	3	4	y
0	1	2	3	4	5	x + 1
1	2	3	4	5	6	y + 2
2	3	5	7	9	11	2y + 3
3	5	13	29	61	125	8×2^y − 3
4	13	65533	$2^{65536}-3$	$ack(3,2^{65536}-3$	$ack(3,ack(4,3))$	$2^{2^{\dots ^{2}}}-3$ ( $y+3$ Terme)
5	65533	$ack(4,65533)$	$ack(4,ack(5,1))$	Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle ack(4,ack(5,2))}	$ack(4,ack(5,2))$
6	$ack(5,1)$	$ack(5,ack(5,1))$	$ack(5,ack(6,1))$	$ack(5,ack(6,2))$	$ack(5,ack(6,3))$

Intuitive Erklärung

Intuitiv ist die erste Zeile der Wertetabelle (genauer: die Werte von Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle ack(0,y)} ) einfach eine Liste aller natürlichen Zahlen, und die angewandte mathematische Operation ist die Addition einer 1 zu $y$ . Alle folgenden Zeilen enthalten einfach Anweisungen, in dieser Zeile einen Wert zu suchen. Im Falle der Zeile $x=1$ vereinfacht sich diese Anweisung dahingehend, den Wert $ack(0,y+1)$ in der Zeile $x=0$ zu suchen, aber diese Vereinfachung ist schon etwas schwieriger herzuleiten – zum Beispiel:

 
ack(1, 2) = ack(0, ack(1,1))
          = ack(0, ack(0, ack(1,0)))
          = ack(0, ack(0, 2))
          = ack(0, 3)
          = 4

Wir betrachten nun einen komplexeren Fall, nämlich $ack(4,3)$ , den ersten Funktionswert, der so groß ist, dass er praktisch nicht dezimal aufgeschrieben werden kann.

ack(4, 3) = ack(3, ack(4, 2))
          = ack(3, ack(3, ack(4, 1)))
          = ack(3, ack(3, ack(3, ack(4, 0))))
          = ack(3, ack(3, ack(3, ack(3, 1))))
          = ack(3, ack(3, ack(3, ack(2, ack(3, 0)))))
          = ack(3, ack(3, ack(3, ack(2, ack(2, 1)))))
          = ack(3, ack(3, ack(3, ack(2, ack(1, ack(2, 0))))))
          = ack(3, ack(3, ack(3, ack(2, ack(1, ack(1, 1))))))
          = ack(3, ack(3, ack(3, ack(2, ack(1, ack(0, ack(1, 0)))))))
          = ack(3, ack(3, ack(3, ack(2, ack(1, ack(0, ack(0, 1)))))))
          = ack(3, ack(3, ack(3, ack(2, ack(1, ack(0, 2))))))
          = ack(3, ack(3, ack(3, ack(2, ack(1, 3)))))
          = ack(3, ack(3, ack(3, ack(2, ack(0, ack(1, 2))))))
          = ack(3, ack(3, ack(3, ack(2, ack(0, ack(0, ack(1, 1)))))))
          = ack(3, ack(3, ack(3, ack(2, ack(0, ack(0, ack(0, ack(1, 0))))))))
          = ack(3, ack(3, ack(3, ack(2, ack(0, ack(0, ack(0, ack(0, 1))))))))
          = ack(3, ack(3, ack(3, ack(2, ack(0, ack(0, ack(0, 2))))))
          = ack(3, ack(3, ack(3, ack(2, ack(0, ack(0, 3)))))
          = ack(3, ack(3, ack(3, ack(2, ack(0, 4)))))
          = ack(3, ack(3, ack(3, ack(2, 5))))

Das ist für einige Zeit der einfachste Fall einer solchen Expansion, und es ist nun offensichtlich, warum Funktionswerte wie dieser in der obigen Tabelle selten direkt berechnet werden. Es ist auch interessant festzustellen, wie viele Schritte nötig sind, um schon sehr einfach aussehende Ackermann-Ausdrücke zu vereinfachen. Jede Zeile im vorigen Beispiel ist eine einzige Anwendung eines der drei Teile der Definition der Ackermannfunktion. Wenn wir an dieser Stelle mehrere logische Schritte überspringen, könnten wir $ack(2,5)$ zu 13 auswerten und dann versuchen, Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle ack(3,13)} auszuwerten – das ist 8179. Der nächste Funktionsaufruf, $ack(3,8179)$ , liefert eine Zahl, die der Zahl der Atome im Universum entspricht, einige Dutzend mal mit sich selbst multipliziert. Diese Zahl $n$ wird schließlich in die Berechnung $ack(3,n)$ eingesetzt, der irgendwann zu einem Ausdruck der Form $ack(2,ack(2,ack(2,\dots ack(2,0)\dots )))$ ausgeschrieben würde, der aber mit unseren Mitteln nicht mehr aufgeschrieben werden kann.

Der wirklich faszinierende Aspekt der Ackermann-Funktion ist, dass die einzige Berechnung, die neben den rekursiven Aufrufen tatsächlich auftaucht, die Berechnung von $ack(0,n)$ ist, die einfach $n$ um 1 erhöht.

Explizite Beschreibung

Intuitiv definiert die Ackermannfunktion eine verallgemeinerte Multiplikation mit 2 durch iterierte Additionen und eine Exponentialfunktion zur Basis 2 durch iterierte Multiplikationen, weiter Iterationen dieser Operation usw. Am knappsten kann sie nicht-rekursiv mithilfe von Conway-Kettenpfeilen ...

ack(x,y)=2\rightarrow (y+3)\rightarrow (x-2)-3

... oder mit Hyper-Operatoren ausgedrückt werden:

A(x,y)=\mathrm {hyper} (2,x,y+3)-3

Geschichte

1928 betrachtete Wilhelm Ackermann eine Funktion $A(x,y,z)$ von drei Variablen, die $z$ -fache iterierte Potenzierung von $x$ mit $y$ oder $x\to y\to z$ in Conways Notation. Er bewies, dass dies eine rekursive Funktion ist, die nicht primitiv-rekursiv ist. Diese Definition wurde später von Hans Hermes bzw. Rozsa Peter and Raphael Robinson zu der obigen Definition mit zwei Argumenten vereinfacht.

Inverse

Da die oben betrachtete Funktion $f(n):=ack(n,n)$ sehr schnell wächst, wächst ihre Inverse sehr langsam. Diese Inverse taucht in der Laufzeitanalyse bestimmter Algorithmen auf. In diesem und anderen Zusammenhängen wird die Ackermannfunktion oft leicht umdefiniert zu einer Funktion mit ähnlichem asymptotischem Verhalten, aber ohne die $-3$ -Terme, oder aber mit den Potenzen von 2 in Zeile 0, wobei die Zeilen 0-2 der ursprünglichen Definition ausgelassen werden. Diese modifizierten Funktionen sind nicht äquivalent zur Ackermannfunktion, aber nach den Maßstäben der Laufzeitanalyse können sie als äquivalent betrachtet werden. Die Inverse der Funktion $f$ ist für jede vorstellbare Eingabegröße kleiner als 4, kann also in der praktischen Analyse von Algorithmen als konstant betrachtet werden.

Einsatz als Benchmark

Auf Grund ihrer extremen Rekursionstiefe kann die Ackermannfunktion als Benchmark für die Fähigkeit eines Compilers, Rekursion zu optimieren, verwendet werden. Zum Beispiel kann ein Compiler, der "erkennt", dass $ack(3,30)$ etwas unterhalb einer Potenz von 2 liegt oder der Zwischenergebnisse wie $ack(3,n)$ und $ack(2,n)$ speichern kann, statt sie neu zu berechnen, die Berechnung von $ack$ um das Hundert- bis Tausendfache beschleunigen. Außerdem erhält man einen bedeutenden Zeitvorteil, wenn man $ack(1,n)$ direkt berechnet, statt es rekursiv zu $ack(1,ack(1,ack(1,\dots ack(1,0)\dots )))$ zu expandieren. Die direkte Berechnung von $ack(1,n)$ erfordert lineare Zeit in $n$ . Die Berechnung von $ack(2,n)$ erfordert quadratische Zeit, denn sie führt zu $O(n)$ verschachtelten Aufrufen von $ack(1,i)$ für verschiedene $i$ . Die Berechnung von $ack(3,n)$ erfordert schließlich eine zu $4^{n+1}$ proportionale Zeit.

Es sei noch festgehalten, dass der Wert $ack(4,2)$ , der in Dezimalschreibweise auf verschiedenen Internetseiten auftaucht, wahrscheinlich nicht mit der rekursiven Definition der Ackermannfunktion praktisch berechnet werden kann.

Weblinks

Einige Werte der Ackermannfunktion (Englisch)
Beispielanwendung der Ackermannfunktion als Benchmark. Beachten Sie die große Zahl der Funktionsaufrufe schon bei der Berechnung kleiner Werte (Englisch)
Dezimaler Wert von ack(4,2)