WikiDer > Ackermann-Funktion

Das Ackermann-Funktion (benannt nach Wilhelm Ackermann) ist ein Beispiel für eine Summe, kalkulierbarFunktion das nicht primitiv rekursiv ist. Es ist eines der bekanntesten Beispiele für eine Funktion, die mehr als exponentiell steigt an.

Definition

Das Ackermann-Funktion hat zwei natürliche Zahlen${displaystyle m}$ und ${displaystyle n}$ als Argumente und lautet wie folgt^[1] (rekursiv) definiert:

${displaystyle { egin{array}{lcl}operatorname {A} (0,n)&=&n 1/operatorname {A} (m,0)&=&operatorname {A} (m-1,1)&{mbox{ if }}m>0/operatorname {A} (m,n)&=&operatorname {A} (m-1,A(m,n-1))&{mbox{if }}m>0{mbox{ and }}n>0end{array}}}$

Eigenschaften

Diese Funktion ist für alle Werte von ${displaystyle m}$ und ${displaystyle n}$ definiert, das heißt für alle Werte von all ${displaystyle m}$ und ${displaystyle n}$ die Berechnung hört immer auf. Dies ist der Fall, da bei jedem rekursiven Aufruf der Funktion entweder das erste Argument ${displaystyle m}$ fällt, oder das erste Argument ${displaystyle m}$ bleibt gleich und das zweite Argument ${displaystyle n}$ Tropfen. Auch im zweiten Fall fällt schließlich das erste Argument, nämlich wenn ${displaystyle n}$ ist auf 0 gefallen. Daher tritt der Basisfall immer irgendwann auf ${Anzeigestil A(0,n)}$ auf.

Die Ackermann-Funktion nimmt bereits bei kleinen Werten von ${displaystyle m}$ und ${displaystyle n}$ sehr große Werte: Die Eingabewerte (4, 3) ergeben eine Zahl mit mehr Ziffern, als es Elementarteilchen im sichtbaren Universum gibt.

Beispiel

Das Ackermann-Funktion von ${displaystyle m=1}$ und ${Anzeigestil n=1}$ berechnet sich wie folgt:

${Anzeigestil A(1,1)=A(0,A(1,0))}$

darin ist

${Anzeigestil A(1,0)=A(0.1)=2}$

So

${Anzeigestil A(0,A(1,0))=A(0,2)=3}$

Verweise