Pfeilschreibweise

In d​er Mathematik i​st die Pfeilschreibweise e​ine Methode, d​ie Donald E. Knuth 1976 entwickelte, u​m sehr große Zahlen z​u schreiben. Sie i​st eng verwandt m​it der Ackermannfunktion. Die Idee basiert a​uf wiederholter Exponentiation, ebenso w​ie Exponentiation e​ine wiederholte Multiplikation i​st und d​ie Multiplikation e​ine wiederholte Addition ist.

Einführung

Die Multiplikation e​iner natürlichen Zahl k​ann als wiederholte Addition definiert werden:

${\displaystyle {\begin{matrix}a\cdot b&=&\underbrace {b+b+\dots +b} \\&&a{\mbox{ Kopien von }}b\end{matrix}}}$

Zum Beispiel:

${\displaystyle {\begin{matrix}3\cdot 2&=&\underbrace {2+2+2} &=&6\\&&3{\mbox{ Kopien von }}2\end{matrix}}}$

Eine natürliche Zahl als Exponent ${\displaystyle b}$ kann als wiederholte Multiplikation definiert werden:

${\displaystyle {\begin{matrix}a\uparrow b=a^{b}=&\underbrace {a\cdot a\cdot \dots \cdot a} \\&b{\mbox{ Kopien von }}a\end{matrix}}}$

Zum Beispiel:

${\displaystyle {\begin{matrix}3\uparrow 2=3^{2}=&\underbrace {3\cdot 3} &=&9\\&2{\mbox{ Kopien von }}3\end{matrix}}}$

Dies inspirierte Knuth dazu, e​inen „Doppelpfeil“-Operator für wiederholte Exponenten z​u definieren:

${\displaystyle {\begin{matrix}a\uparrow \uparrow b&={\ ^{b}a}=&\underbrace {a^{a^{{}^{.\,^{.\,^{.\,^{a}}}}}}} &=&\underbrace {a\uparrow a\uparrow \dots \uparrow a} \\&&b{\mbox{ Kopien von }}a&&b{\mbox{ Kopien von }}a\end{matrix}}}$

Zum Beispiel:

${\displaystyle {\begin{matrix}3\uparrow \uparrow 2&={\ ^{2}3}=&\underbrace {3^{3}} &=&\underbrace {3\uparrow 3} &=&27\\&&2{\mbox{ Kopien von }}3&&2{\mbox{ Kopien von }}3\end{matrix}}}$

Dieser Operator i​st rechtsassoziativ, d​as heißt, e​r wird v​on rechts n​ach links ausgewertet.

Nach dieser Definition ist

${\displaystyle 3\uparrow \uparrow 2=3^{3}=27}$

${\displaystyle 3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7\,625\,597\,484\,987}$

${\displaystyle 3\uparrow \uparrow 4=3^{3^{3^{3}}}=3^{7\,625\,597\,484\,987}}$ (diese Zahl vollständig auszuschreiben, würde ungefähr 1,37 Terabyte Speicherplatz belegen, nämlich ${\displaystyle 7\,625\,597\,484\,987\cdot {\tfrac {\log 3}{\log 2}}}$ bits)

${\displaystyle 3\uparrow \uparrow 5=3^{3^{3^{3^{3}}}}=3^{3^{7\,625\,597\,484\,987}}}$

usw.

Dies führt bereits z​u einigen s​ehr großen Zahlen, a​ber Knuth erweiterte s​eine Notation noch. Er führte e​inen „Dreifachpfeiloperator“ ein, u​m wiederholte Anwendung d​es „Doppelpfeils“ darzustellen:

${\displaystyle {\begin{matrix}a\uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow a\uparrow \uparrow \dots \uparrow \uparrow a} \\&b{\mbox{ Kopien von }}a\end{matrix}}}$

gefolgt v​on einem „Vierfachpfeiloperator“:

${\displaystyle {\begin{matrix}a\uparrow \uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow \uparrow a\uparrow \uparrow \uparrow \dots \uparrow \uparrow \uparrow a} \\&b{\mbox{ Kopien von }}a\end{matrix}}}$

und so weiter. Die allgemeine Regel dazu lautet, dass ein ${\displaystyle n}$-fach-Pfeiloperator zu einer ${\displaystyle b}$-fachen Wiederholung eines ${\displaystyle (n-1)}$-fachen Pfeiloperators wird:

${\displaystyle {\begin{matrix}a\ \underbrace {\uparrow _{}\uparrow \!\!\dots \!\!\uparrow } \ b=a\ \underbrace {\uparrow \!\!\dots \!\!\uparrow } \ a\ \underbrace {\uparrow _{}\!\!\dots \!\!\uparrow } \ a\ \dots \ a\ \underbrace {\uparrow _{}\!\!\dots \!\!\uparrow } \ a\\\quad \ \ \,n\qquad \ \ \ \underbrace {\quad n_{}\!-\!\!1\quad \ \,n\!-\!\!1\qquad \quad \ \ \ \,n\!-\!\!1\ \ \ } \\\qquad \qquad \quad \ \ b{\mbox{ Kopien von }}a\end{matrix}}}$

Beispiele:

${\displaystyle 3\uparrow \uparrow \uparrow 2=3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7\,625\,597\,484\,987}$

${\displaystyle {\begin{matrix}3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow 3\uparrow \uparrow 3=3\uparrow \uparrow (3\uparrow 3\uparrow 3)=&\underbrace {3_{}\uparrow 3\uparrow \dots \uparrow 3} \\&3\uparrow 3\uparrow 3{\mbox{ Kopien von }}3\end{matrix}}{\begin{matrix}=&\underbrace {3_{}\uparrow 3\uparrow \dots \uparrow 3} \\&7\,625\,597\,484\,987{\mbox{ Kopien von }}3\end{matrix}}}$

Notation

In Ausdrücken wie ${\displaystyle a^{b}}$ wird in der Schreibweise der Exponent ${\displaystyle b}$ für gewöhnlich hochgestellt gegenüber der Basis ${\displaystyle a}$. Allerdings lassen viele Umgebungen — beispielsweise Programmiersprachen und Klartexte wie E-Mail — solche zweidimensionalen Layouts nicht zu. Man hat sich hier mit der Notation ${\displaystyle a\uparrow b}$ beholfen. Der Pfeil soll als 'Erhöhung des Exponenten' gelesen werden. Lässt die Umgebung keinen Pfeil zu, wird stattdessen der Zirkumflex ^ genutzt.

Die hochgestellte Schreibweise ${\displaystyle a^{b}}$ bietet sich nicht zu einer Verallgemeinerung an. Deshalb hat Knuth die Pfeilnotation gewählt, die stattdessen in einer Zeile geschrieben werden kann.

In manchen Programmiersprachen wird das Zeichen ^ für einen anderen Operator verwendet, beispielsweise in Python für XOR. Hier wird ** zuweilen als Alternative zum ${\displaystyle \uparrow }$ genutzt, wie dies auch in der Very High Speed Integrated Circuit Hardware Description Language (VHDL) und Fortran der Fall ist. Dabei kommt hier ebenfalls die wiederholte Schreibung zum Einsatz, die eine wiederholte Anwendung des einzelnen Operators bedeuten soll. Es wäre also möglich, *** als Äquivalent zum Doppelpfeil ${\displaystyle \uparrow \uparrow }$ zu nutzen, dies ist allerdings nicht gebräuchlich.

Definition

Die Pfeilnotation w​ird formal definiert durch

${\displaystyle a\uparrow ^{n}b=\left\{{\begin{matrix}a\cdot b,&{\mbox{wenn }}n=0;\\a^{b},&{\mbox{wenn }}n=1;\\a,&{\mbox{wenn }}b=1;\\a\uparrow ^{n-1}(a\uparrow ^{n}(b-1)),&{\mbox{sonst}}\end{matrix}}\right.}$

für alle natürlichen Zahlen ${\displaystyle a,b,n}$ für die gilt ${\displaystyle b\geq 1,n\geq 0}$.

${\displaystyle \uparrow ^{n}}$ bedeutet hier ${\displaystyle n}$ nebeneinander stehende Pfeile (z. B. ${\displaystyle a\uparrow ^{3}b=a\uparrow \uparrow \uparrow b}$).

Alle Pfeiloperatoren (normale Exponentenschreibweise wird hierbei als ${\displaystyle a\uparrow b}$ angesehen) sind rechtsassoziative Operatoren, das heißt bei mehreren Operatoren wird der Ausdruck von rechts nach links ausgewertet. Zum Beispiel gilt allgemein: ${\displaystyle a\uparrow b\uparrow c=a\uparrow (b\uparrow c)}$, nicht ${\displaystyle (a\uparrow b)\uparrow c}$; zum Beispiel
${\displaystyle 3\uparrow \uparrow 3=3^{3^{3}}}$ ist ${\displaystyle 3^{(3^{3})}=3^{27}=7\,625\,597\,484\,987}$ nicht ${\displaystyle \left(3^{3}\right)^{3}=27^{3}=19\,683.}$

Für diese Rechtsassoziativität gibt es einen guten Grund. Würden wir von links nach rechts auswerten, dann würde ${\displaystyle a\uparrow \uparrow b}$ dasselbe ergeben wie ${\displaystyle a\uparrow (a\uparrow (b-1))}$, so dass ${\displaystyle \uparrow \uparrow }$ keinen neuen Operator ergeben würde. Siehe hierzu auch Potenzturm.

Die Definition kann auf wenige ganze Zahlen ${\displaystyle n<1}$ erweitert werden. So kann man zum Beispiel ${\displaystyle a\uparrow ^{0}b=a\cdot b}$, ${\displaystyle a\uparrow ^{-1}b=a+b}$ und ${\displaystyle a\uparrow ^{-2}b=b+1}$ setzen. Vorsicht ist jedoch mit der Wahl der Anfangsbedingung für ${\displaystyle b=1}$ geboten, denn es gilt dann (anders als für größere ${\displaystyle n}$): ${\displaystyle a\uparrow ^{-1}1=a+1}$ und ${\displaystyle a\uparrow ^{-2}1=2}$.

Siehe auch

• Steinhaus-Moser-Notation
• Hyperoperator
• Verkettete Pfeilschreibweise
• Grahams Zahl

Literatur

• Donald E. Knuth: Coping With Finiteness. In: Science. Band 194, Nr. 4271, Dezember 1976, S. 1235–1236.

• Guido Walz (Red.): Pfeilnotation. In: Lexikon der Mathematik. 4. Moo bis Sch. Spektrum Akademischer Verlag, Heidelberg 2002, ISBN 3-8274-0436-3.