Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenMittwoch, 18. September 2019 

Ackermannfunktion


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Die Ackermannfunktion wurde 1928 von dem Mathematiker Wilhelm Ackermann definiert. Heute ist die folgende von Hermes vereinfachte Version <math>ack</math> gebräuchlich:
  • <math>ack \left(0 y \right) := y +
  • <math>ack \left(x 0 \right) := ack \left(x 1 1 \right)</math>
  • <math>ack \left(x y \right) := ack \left(x ack \left(x y - 1 \right) \right)</math>
Beispiele:
  • <math>ack \left(2 0\right) = ack \left(1 1\right) ack \left(0 ack \left(1 0\right)\right) = ack ack \left(0 1\right)\right) = ack \left(0 2\right) 3</math>
  • <math>ack \left(1 2\right) = ack \left(0 ack 1\right)\right) = ack \left(0 3\right) = 4</math>
  • <math>ack \left(2 1\right) = ack \left(1 ack 0\right)\right) = ack \left(1 3\right) = ack ack \left(1 2\right)\right) = ack \left(0 4\right) 5</math>
Es gibt noch eine weiter vereinfachte <math>a</math>:
  • <math>a \left(0 y \right) := a \left(x \right) := 1</math>
  • <math>a \left(1 y \right) := 3y +
  • <math>a \left(x y \right) := a \left(x 1 a \left(x - 1 ... a - 1 y \right) ... \right) \right)</math> mal)

<math>a</math> ist WHILE-berechenbar (vgl. WHILE-Programm ) aber auf Grund ihres schnellen Wachstums primitiv-rekursiv (LOOP-berechenbar vgl. LOOP-Programm ).

Auf Grund ihrer tiefen Rekursivität wird Ackermann-Funktion für das Benchmarking verwendet (Berechnungszeit für ack (3   n ) ist O(4 n +1 )).



Bücher zum Thema Ackermannfunktion

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Ackermannfunktion.html">Ackermannfunktion </a>