In der Mathematik ist die Pfeilschreibweise eine Methode, die Donald E. Knuth 1976 entwickelte, um sehr große Zahlen zu schreiben. Sie ist eng verwandt mit der Ackermannfunktion. Die Idee basiert auf wiederholter Exponentiation, ebenso wie Exponentiation eine wiederholte Multiplikation ist und die Multiplikation eine wiederholte Addition ist.
Die Multiplikation einer natürlichen Zahl kann als wiederholte Addition definiert werden:
![{\displaystyle {\begin{matrix}a\cdot b&=&\underbrace {b+b+\dotsb +b} \\&&a{\mbox{ Kopien von ))b\end{matrix))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4ab3de8d00a4e7aa7ea3de5579dc20ead75a8f9f)
Zum Beispiel:
![{\displaystyle {\begin{matrix}3\cdot 2&=&\underbrace {2+2+2} &=&6\\&&3{\mbox{ Kopien von ))2\end{matrix))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0b5e48368217041a7f4862314a9d065601cea8b6)
Eine natürliche Zahl als Exponent
kann als wiederholte Multiplikation definiert werden:
![{\displaystyle {\begin{matrix}a\uparrow b=a^{b}=&\underbrace {a\cdot a\cdot \dotsm \cdot a} \\&b{\mbox{ Kopien von ))a\end{matrix))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eeb44223daa04162bf70ca41562fbd2ef7924637)
Zum Beispiel:
![{\displaystyle {\begin{matrix}3\uparrow 2=3^{2}=&\underbrace {3\cdot 3} &=&9\\&2{\mbox{ Kopien von ))3\end{matrix))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/32315f2d34d118effd01cfba1cb182645968b2e3)
Dies inspirierte Knuth dazu, einen „Doppelpfeil“-Operator für wiederholte Exponenten zu 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))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/49d2b1434e6ebf4d601be0fa90dfea9477b5ce68)
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))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/300fd958a5e784218255e24e2031f050f7e37d4e)
Dieser Operator ist rechtsassoziativ, das heißt, er wird von rechts nach links ausgewertet.
Nach dieser Definition ist
![{\displaystyle 3\uparrow \uparrow 2=3^{3}=27}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5217b6f0699e9e634d31a294211ccbc027f3cd0)
![{\displaystyle 3\uparrow \uparrow 3=3^{3^{3))=3^{27}=7\,625\,597\,484\,987}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05918a69459c2c53cc55438a5fc3720146bc1c93)
(um diese Zahl vollständig als Binärzahl darzustellen, würden ungefähr 1,37 Tebibyte bzw. 1,51 Terabyte benötigt werden, nämlich
bits)
![{\displaystyle 3\uparrow \uparrow 5=3^{3^{3^{3^{3))))=3^{3^{7\,625\,597\,484\,987))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f47b9249251839ab16f441b2c30ceef86b9211a2)
- usw.
Dies führt bereits zu einigen sehr großen Zahlen, aber Knuth erweiterte seine Notation noch. Er führte einen „Dreifachpfeiloperator“ ein, um wiederholte Anwendung des „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))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/be1043d6d22090a58b158159ac40e056bf75fe30)
gefolgt von 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))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5872294ca8f91c63522f179972050e4f2f93377b)
und so weiter. Die allgemeine Regel dazu lautet, dass ein
-fach-Pfeiloperator zu einer
-fachen Wiederholung eines
-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))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/212da38975e8d7e000e47de14ac8402ee1d72e2c)
Beispiele:
In Ausdrücken wie
wird in der Schreibweise der Exponent
für gewöhnlich hochgestellt gegenüber der Basis
. Allerdings lassen viele Umgebungen – beispielsweise Programmiersprachen und Klartexte wie E-Mail – solche zweidimensionalen Layouts nicht zu. Man hat sich hier mit der Notation
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
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 Pfeiloperator
genutzt, wie dies auch in 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
zu nutzen, dies ist allerdings nicht gebräuchlich.
Die Pfeilnotation wird 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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/edb4fd55d1a1cb6e4620e6abd9566169443f5c92)
für alle natürlichen Zahlen
, für die gilt
.
bedeutet hier
nebeneinanderstehende Pfeile (z. B.
).
Alle Pfeiloperatoren (normale Exponentenschreibweise wird hierbei als
angesehen) sind rechtsassoziative Operatoren, das heißt bei mehreren Operatoren wird der Ausdruck von rechts nach links ausgewertet. Zum Beispiel gilt allgemein:
, nicht
;
demnach gilt
=
und nicht
Für diese Rechtsassoziativität gibt es einen guten Grund. Würde von links nach rechts ausgewertet, dann würde
dasselbe ergeben wie
, sodass
keinen neuen Operator ergeben würde. Siehe hierzu auch Potenzturm.
Die Definition kann auf wenige ganze Zahlen
erweitert werden. So kann man zum Beispiel
,
und
setzen. Vorsicht ist jedoch mit der Wahl der Anfangsbedingung für
geboten, denn es gilt dann (anders als für größere
):
und
.