Die Ackermannfunktion
Die Ackermannfunktion ist eine 1926 von Wilhelm Ackermann gefundene, extrem schnell wachsende mathematische Funktion, mit deren Hilfe in der theoretischen Informatik Grenzen von Computer- und Berechnungsmodellen aufgezeigt werden können. Heute gibt es eine ganze Reihe von Funktionen, die als Ackermannfunktion bezeichnet werden. Diese weisen alle ein ähnliches Bildungsgesetz wie die ursprüngliche Ackermannfunktion auf und haben auch ein ähnliches Wachstumsverhalten.
Geschichte
1926 vermutete David Hilbert, dass jede berechenbare Funktion primitiv-rekursiv sei. Vereinfacht bedeutet dies, dass sich jede durch einen Computer berechenbare Funktion aus einigen wenigen, sehr einfachen Regeln zusammensetzen lässt und dass sich die Dauer der Berechnung im Voraus abschätzen lässt. Dies trifft auf nahezu alle in der Praxis vorkommenden Funktionen zu.
Ebenfalls 1926 konstruierte Ackermann eine Funktion, die diese Vermutung widerlegt, und veröffentlichte sie 1928. Ihm zu Ehren wird diese Funktion heute Ackermannfunktion genannt. Sie kann von einem Computer in endlicher Zeit ausgewertet werden, ist aber nicht primitiv-rekursiv.
1955 konstruierte Rózsa Péter eine vereinfachte Version, die die gleichen Eigenschaften besitzt. Diese Funktion, gelegentlich auch als Ackermann-Péter-Funktion bezeichnet, wird heute vorwiegend benutzt.
Implementierung
Delphi-Quellcode:
function ackermann(n, m: Integer): Integer;
begin
if n = 0 then
result := m + 1
else
if m = 0 then
result := ackermann(n - 1, 1)
else
result := ackermann(n - 1, ackermann(n, m - 1));
end;
[edit=MrSpock]Ein paar unbedeutende Zuweisungszeichen eingefügt und n und m im Prozedurkopf einen Typ zugewiesen. Mfg, MrSpock[/edit]
[edit=Matze]Dieses Thema reicht nicht ganz aus, um in die Code-Library aufgenommen zu werden. MfG, Matze[/edit]
Antwort
Zitat
Linear-Darstellung
