imported>Sullafelix: /* Literatur */ Die abschließende 5 fehlte im DOI des Knuth-Aufsatzes

2025-11-16T14:10:43Z

Literatur: Die abschließende 5 fehlte im DOI des Knuth-Aufsatzes

Neue Seite

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.

== Einführung ==

Die [[Multiplikation]] einer [[Natürliche Zahl|natürlichen Zahl]] kann als wiederholte [[Addition]] definiert werden:

:<math>
\begin{matrix}
a \cdot b & = & \underbrace{b+b+\dotsb+b} \\
& & a\mbox{ Kopien von }b
\end{matrix}
</math>

Zum Beispiel:

:<math>
\begin{matrix}
3\cdot 2 & = & \underbrace{2+2+2} & = & 6\\
& & 3\mbox{ Kopien von }2
\end{matrix}
</math>

Eine natürliche Zahl als [[Potenz (Mathematik)|Exponent]] <math>b</math> kann als wiederholte Multiplikation definiert werden:

:<math>
\begin{matrix}
a\uparrow b= a^b = & \underbrace{a\cdot a\cdot\dotsm\cdot a}\\
& b\mbox{ Kopien von }a
\end{matrix}
</math>

Zum Beispiel:

:<math>
\begin{matrix}
3\uparrow 2= 3^2 = & \underbrace{3\cdot 3} & = & 9\\
& 2\mbox{ Kopien von }3
\end{matrix}
</math>

Dies inspirierte Knuth dazu, einen „Doppelpfeil“-[[Operator (Mathematik)|Operator]] für wiederholte Exponenten zu definieren:

:<math>
\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}
</math>

Zum Beispiel:

:<math>
\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}
</math>

Dieser Operator ist [[Rechtsassoziativität|rechtsassoziativ]], das heißt, er wird von rechts nach links ausgewertet.

Nach dieser Definition ist
:<math>3\uparrow\uparrow2=3^3=27 </math>
:<math>3\uparrow\uparrow3=3^{3^3}=3^{27}=7\,625\,597\,484\,987 </math>
:<math>3\uparrow\uparrow4=3^{3^{3^3}}=3^{7\,625\,597\,484\,987} </math> (um diese Zahl vollständig als [[Dualsystem|Binärzahl]] darzustellen, würden ungefähr 1,37 [[Tebibyte]] bzw. 1,51 [[Terabyte]] benötigt werden, nämlich <math>7\,625\,597\,484\,987 \cdot \tfrac{\log 3}{\log 2}</math> bits)
:<math>3\uparrow\uparrow5=3^{3^{3^{3^3}}} = 3^{3^{7\,625\,597\,484\,987}} </math>
: 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:

:<math>
\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}
</math>

gefolgt von einem „Vierfachpfeiloperator“:

:<math>
\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}
</math>

und so weiter. Die allgemeine Regel dazu lautet, dass ein <math>n</math>-fach-Pfeiloperator zu einer <math>b</math>-fachen Wiederholung eines <math>(n - 1)</math>-fachen Pfeiloperators wird:

:<math>
\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}
</math>

Beispiele:

<math>3\uparrow\uparrow\uparrow2 = 3\uparrow\uparrow3 = 3^{3^3} = 3^{27}=7\,625\,597\,484\,987</math>

<math>
\begin{matrix}
3\uparrow\uparrow\uparrow3 = 3\uparrow\uparrow3\uparrow\uparrow3 = 3\uparrow\uparrow(3\uparrow3\uparrow3) = &
\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}
</math>

== Notation ==

In Ausdrücken wie <math>a^b</math> wird in der Schreibweise der Exponent <math>b</math> für gewöhnlich hochgestellt gegenüber der Basis <math>a</math>. Allerdings lassen viele Umgebungen – beispielsweise [[Programmiersprache]]n und Klartexte wie [[E-Mail]] – solche zweidimensionalen Layouts nicht zu. Man hat sich hier mit der Notation <math>a \uparrow b</math> beholfen. Der [[Pfeil (Symbol)|Pfeil]] soll als „Erhöhung des Exponenten“ gelesen werden. Lässt die Umgebung keinen Pfeil zu, wird stattdessen der [[Zirkumflex]] <code>^</code> genutzt.

Die hochgestellte Schreibweise <math>a^b</math> 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 <code>^</code> für einen anderen Operator verwendet, beispielsweise in [[Python (Programmiersprache)|Python]] für [[XOR]]. Hier wird <code>**</code> zuweilen als Alternative zum Pfeiloperator <math>\uparrow</math> genutzt, wie dies auch in [[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, <code>***</code> als Äquivalent zum Doppelpfeil <math>\uparrow\uparrow</math> zu nutzen, dies ist allerdings nicht gebräuchlich.

== Definition ==

Die Pfeilnotation wird formal definiert durch

:<math>
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.
</math>
für alle natürlichen Zahlen <math>a, b, n</math>, für die gilt <math>b \ge 1, n \ge 0</math>.

<math>\uparrow^n</math> bedeutet hier <math>n</math> nebeneinanderstehende Pfeile (z. B. <math>a \uparrow^3 b = a \uparrow \uparrow \uparrow b </math>).

Alle Pfeiloperatoren (normale Exponentenschreibweise wird hierbei als <math>a \uparrow b</math> angesehen) sind [[Rechtsassoziativität|rechtsassoziative Operatoren]], das heißt bei mehreren Operatoren wird der Ausdruck von rechts nach links ausgewertet. Zum Beispiel gilt allgemein: <math>a \uparrow b \uparrow c = a \uparrow (b \uparrow c)</math>, nicht <math>(a \uparrow b) \uparrow c</math>;<br />demnach gilt <math>3\uparrow\uparrow 3=3^{3^3}</math>= <math>3^{(3^3)}=3^{27}=7\,625\,597\,484\,987</math> und nicht <math>\left(3^3\right)^3=27^3=19\,683.</math>

Für diese Rechtsassoziativität gibt es einen guten Grund. Würde von links nach rechts ausgewertet, dann würde <math>a \uparrow\uparrow b</math> dasselbe ergeben wie <math>a \uparrow (a \uparrow (b - 1))</math>, sodass <math>\uparrow\uparrow</math> keinen neuen Operator ergeben würde. Siehe hierzu auch [[Potenzturm]].

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

== Siehe auch ==

* [[Steinhaus-Moser-Notation]]
* [[Hyperoperator]]
* [[Verkettete Pfeilschreibweise]]
* [[Grahams Zahl]]

== Literatur ==

* {{Literatur
|Autor=[[Donald E. Knuth]]
|Titel=Coping with Finiteness
|Sammelwerk=[[Science]]
|Band=194
|Nummer=4271
|Datum=1976-12
|Seiten=1235–1236
|DOI=10.1126/science.194.4271.1235}}
* {{Literatur
|Hrsg=Guido Walz
|Titel=Pfeilnotation
|Sammelwerk=Lexikon der Mathematik
|Band=Band 4: ''Moo bis Sch''
|Verlag=Spektrum Akademischer Verlag
|Ort=Heidelberg u. a.
|Datum=2002
|ISBN=3-8274-0436-3}}

== Weblinks ==
* {{MathWorld|id=KnuthUp-ArrowNotation|title=Knuth Up-Arrow Notation}}

[[Kategorie:Mathematische Notation]]
[[Kategorie:Potenz (Mathematik)]]

Pfeilschreibweise - Versionsgeschichte

imported>Sullafelix: /* Literatur */ Die abschließende 5 fehlte im DOI des Knuth-Aufsatzes