In der Mathematik ist die-Pfeil-Notation von Knuth eine Methode der Notation für sehr große ganze Zahlen, die von Donald Knuth 1976 eingeführt sind. Es ist nah mit der Funktion von Ackermann und besonders mit der Hyperoperationsfolge verbunden. Die Idee basiert auf der Tatsache, dass Multiplikation als wiederholte Hinzufügung und exponentiation als wiederholte Multiplikation angesehen werden kann. Das Weitergehen auf diese Weise führt zu wiederholtem exponentiation (tetration) und zum Rest der Hyperoperationsfolge, die mit der Pfeil-Notation von Knuth allgemein angezeigt wird.

Einführung

Die gewöhnlichen arithmetischen Operationen der Hinzufügung, Multiplikation und exponentiation werden in eine Folge von Hyperoperationen wie folgt natürlich erweitert.

Die Multiplikation durch eine natürliche Zahl wird als wiederholte Hinzufügung definiert:

:

\begin {Matrix-}\

a\times b & = & \underbrace {a+a +\dots+a} \\

& & b\mbox {Kopien} ein

\end {Matrix}

</Mathematik>

Zum Beispiel,

:

\begin {Matrix} 4\times 3 & = & \underbrace {4+4+4} & = & 12 \\

& & 3\mbox {Kopien} 4

\end {Matrix} </Mathematik>

Exponentiation für eine natürliche Macht wird als wiederholte Multiplikation, der durch einen einzelnen-Pfeil angezeigter Knuth definiert:

: \begin {Matrix-}\

a\uparrow b = a^b = & \underbrace {a\times a\times\dots\times ein }\\\

& b\mbox {Kopien} ein

\end {Matrix} </Mathematik>Zum Beispiel,: \begin {Matrix-}\

4\uparrow 3 = 4^3 = & \underbrace {4\times 4\times 4} & = & 64 \\

& 3\mbox {Kopien} 4

\end {Matrix} </Mathematik>

Um die Folge von Operationen außer exponentiation zu erweitern, hat Knuth einen "doppelten Pfeil" Maschinenbediener definiert, um wiederholten exponentiation (tetration) anzuzeigen:

: \begin {Matrix-}\

a\uparrow\uparrow b & = {\\^ {b} a\= & \underbrace {a^ {a^}}}} &

= & \underbrace {a\uparrow (a\uparrow (\dots\uparrow a))}

\\

& & b\mbox {Kopien} ein

& & b\mbox {Kopien} ein

\end {Matrix-}\

</Mathematik>Zum Beispiel,: \begin {Matrix-}\

4\uparrow\uparrow 3 & = {\\^ {3} 4\= & \underbrace {4^ {4^4}} &

= & \underbrace {4\uparrow (4\uparrow 4)} & = & 4^ {256} & \approx & 1.34078079\times 10^ {154}

& \\

& & 3\mbox {Kopien} 4

& & 3\mbox {Kopien} 4 \end {Matrix} </Mathematik>

Hier und unter der Einschätzung soll vom Recht bis linken stattfinden, weil die Pfeil-Maschinenbediener von Knuth (gerade wie exponentiation) definiert werden, um richtig-assoziativ zu sein.

Gemäß dieser Definition,

::::

:etc.

Das führt bereits zu einer ziemlich großen Anzahl, aber Knuth hat die Notation erweitert. Er hat fortgesetzt, einen "dreifachen Pfeil" Maschinenbediener für die wiederholte Anwendung des "doppelten Pfeils" Maschinenbediener (auch bekannt als pentation) zu definieren:

: \begin {Matrix-}\

a\uparrow\uparrow\uparrow b =

&

\underbrace {a_ {}\\uparrow\uparrow (a\uparrow\uparrow (\dots\uparrow\uparrow a)) }\\\

& b\mbox {Kopien} ein

\end {Matrix-}\ </Mathematik>

gefolgt von einem 'vierfachen Pfeil' Maschinenbediener (auch bekannt als hexation):

: \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} ein \end {Matrix-}\ </Mathematik>

und so weiter. Die allgemeine Regel besteht darin, dass - sich Pfeil-Maschinenbediener in eine richtig-assoziative Reihe - Pfeil-Maschinenbediener ausbreitet. Symbolisch,

: \begin {Matrix-}\

a\\underbrace {\\uparrow_ {}\\uparrow \! \!\dots \! \!\uparrow} _ {n }\\b=

\underbrace {a\\underbrace {\\uparrow \! \!\dots \! \!\uparrow} _ {n-1 }\

\(a\\underbrace {\\uparrow_ {}\\! \! \dots \! \!\uparrow} _ {n-1 }\

\(\dots

\\underbrace {\\uparrow_ {}\\! \! \dots \! \!\uparrow} _ {n-1 }\

\a))} _ {b\text {Kopien} ein }\

\end {Matrix-}\ </Mathematik>Beispiele::: \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\uparrow3\uparrow3\mbox {Kopien} 3

\end {Matrix-}\ \begin {Matrix-}\

= & \underbrace {3_ {}\\uparrow 3\uparrow\dots\uparrow 3} \\

& \mbox {7,625,597,484,987 Kopien von 3 }\

\end {Matrix-}\ </Mathematik>

Die Notation wird allgemein verwendet, um mit n Pfeilen anzuzeigen.

Notation

In Ausdrücken solcher als soll die Notation für exponentiation gewöhnlich die Hochzahl als ein Exponent zum Basiswert schreiben. Aber viele Umgebungen - wie Programmiersprachen und Klartext-E-Mail - unterstützen solches zweidimensionales Lay-Out nicht. Leute haben die geradlinige Notation für solche Umgebungen angenommen; der-Pfeil deutet an, 'zur Macht zu erheben'. Wenn die Codierung Pfeil nicht enthält, wird das Auslassungszeichen ^ stattdessen verwendet.

Die hochgestellte Notation leiht sich gut zur Generalisation nicht, die erklärt, warum Knuth beschlossen hat, aus der Reihennotation stattdessen zu arbeiten.

-Pfeil-Notation in Bezug auf Mächte ausschreibend

Der Versuch, das Verwenden der vertrauten hochgestellten Notation zu schreiben, gibt einen Macht-Turm.

:For-Beispiel:

Wenn b eine Variable ist (oder zu groß ist), könnte der Macht-Turm mit Punkten und einem Zeichen geschrieben werden, das die Höhe des Turms anzeigt.

:

Mit dieser Notation weitergehend, konnte mit einem Stapel solcher Macht-Türme, jeder geschrieben werden, die Größe von derjenigen darüber beschreibend.

:

\underbrace {a^ {a^ {.^ {.^ {.}}}}} _ {\underbrace {a^ {a^ {.^ {.^ {.}}}}} _ {\underbrace {a^ {a^ {.^ {.^ {.}}}}} _}} </Mathematik>

Wieder, wenn b eine Variable ist oder zu groß ist, könnte der Stapel mit Punkten und einem Zeichen geschrieben werden, das seine Höhe anzeigt.

:

\left. \underbrace {a^ {a^ {.^ {.^ {.}}}}} _ {\underbrace {a^ {a^ {.^ {.^ {.}}}}} _ {\underbrace {\\vdots} _}} \right\} b </Mathematik>

Außerdem, könnte mit mehreren Säulen solcher Stapel von Macht-Türmen, jede Säule geschrieben werden, die die Zahl von Macht-Türmen im Stapel an seiner linken Seite beschreibt:

:

\left.\left.\left. \underbrace {a^ {a^ {.^ {.^ {.}}}}} _ {\underbrace {a^ {a^ {.^ {.^ {.}}}}} _ {\underbrace {\\vdots} _}} \right\}\

\underbrace {a^ {a^ {.^ {.^ {.}}}}} _ {\underbrace {a^ {a^ {.^ {.^ {.}}}}} _ {\underbrace {\\vdots} _}} \right\}\

\underbrace {a^ {a^ {.^ {.^ {.}}}}} _ {\underbrace {a^ {a^ {.^ {.^ {.}}}}} _ {\underbrace {\\vdots} _}} \right\}\

</Mathematik>

Und mehr allgemein:

:

\underbrace {\

\left.\left.\left. \underbrace {a^ {a^ {.^ {.^ {.}}}}} _ {\underbrace {a^ {a^ {.^ {.^ {.}}}}} _ {\underbrace {\\vdots} _}} \right\}\

\underbrace {a^ {a^ {.^ {.^ {.}}}}} _ {\underbrace {a^ {a^ {.^ {.^ {.}}}}} _ {\underbrace {\\vdots} _}} \right\}\

\cdots \right\}\

ein

} _ {b} </Mathematik>

Das könnte unbestimmt ausgeführt werden, um wie wiederholt, exponentiation von wiederholtem exponentiation für jeden a, n und b zu vertreten (obwohl es klar ziemlich beschwerlich wird).

Das Verwenden tetration

Die tetration Notation erlaubt uns, diese Diagramme ein bisschen einfacher zu machen, während sie noch eine geometrische Darstellung verwendet (wir konnten diese tetration Türme nennen).

:::

\left. \underbrace {^ {^ {^ {^ {^.}.}.} a\a\_ {\underbrace {^ {^ {^ {^ {^.}.}.} a\a\_ {\underbrace {\\vdots} _}} \right\} b </Mathematik>

Schließlich, als ein Beispiel konnte die vierte Zahl von Ackermann als vertreten werden:

:

\underbrace {^ {^ {^ {^ {^ {4}.}.}.} 4\4\_ {\underbrace {^ {^ {^ {^ {^ {4}.}.}.} 4\4\_ {^ {^ {^ {4} 4} 4} 4}} </Mathematik>

Generalisationen

Einige Zahlen sind so groß, dass vielfache Pfeile der-Pfeil-Notation von Knuth zu beschwerlich werden; dann ist ein schmaler Maschinenbediener (und auch für Beschreibungen mit einer variablen Zahl von Pfeilen), oder gleichwertig, hyper Maschinenbediener nützlich.

Einige Zahlen sind so groß, dass sogar, dass Notation nicht genügend ist. Die Zahl von Graham ist ein Beispiel. Conways gekettete Pfeil-Notation kann dann verwendet werden: Eine Kette von drei Elementen ist mit den anderen Notationen gleichwertig, aber eine Kette vier oder mehr ist noch stärker.

: \begin {Matrix-}\

a\uparrow^n b & = & \mbox {hyper} (a, n+2, b) & = & a\to b\to n \\

\mbox {(Knuth)} & & & & \mbox {(Conway) }\

\end {Matrix-}\ </Mathematik>

Es wird allgemein darauf hingewiesen, dass der Pfeil von Knuth für kleinere Umfang-Zahlen, und den verketteten Pfeil oder die hyper Maschinenbediener für größere verwendet werden sollte.

Definition

Die-Pfeil-Notation wird durch formell definiert

:

A\uparrow^n b=

\left\{\

\begin {Matrix-}\

a^b, & \mbox {wenn} n=1; \\

1, & \mbox {wenn} b=0; \\

A\uparrow^ {n-1} (A\uparrow^n (b-1)), & \mbox {sonst }\

\end {Matrix-}\

\right.

</Mathematik>

für alle ganzen Zahlen damit.

Alle-Pfeil-Maschinenbediener (einschließlich normalen exponentiation,) sind assoziativ Recht, d. h. Einschätzung soll vom Recht bis linken in einem Ausdruck stattfinden, der zwei oder mehr solche Maschinenbediener enthält. Zum Beispiel, nicht; zum Beispiel

ist nicht

Es gibt guten Grund für die Wahl dieser Ordnung des Rechts-zu-link der Einschätzung. Wenn wir zum Recht nach links Einschätzung verwendet haben, dann gleichkommen würden

, so dass keine im Wesentlichen neue Operation sein würde.

Recht associativity ist auch natürlich, weil wir den wiederholten Pfeil-Ausdruck umschreiben können, der erscheint

in der Vergrößerung als

, so dass alle s erscheinen

wie verlassen, operands Pfeil-Maschinenbediener. Das ist bedeutend, da die Pfeil-Maschinenbediener nicht auswechselbar sind.

Wenn wir

für die bth funktionelle Macht der Funktion schreiben, haben wir.

Die Definition konnte ein Schritt extrapoliert werden, damit anfangend, wenn n = 0, weil exponentiation wiederholte Multiplikation ist, die mit 1 anfängt. Das Extrapolieren eines Schritts mehr, das Schreiben der Multiplikation als wiederholte Hinzufügung, sind nicht als aufrichtig, weil Multiplikation wiederholte Hinzufügung ist, die mit 0 statt 1 anfängt. "Das Extrapolieren" wieder eines Schritts mehr, das Schreiben der Hinzufügung von n als wiederholte Hinzufügung von 1, verlangen das Starten mit der Zahl a. Vergleichen Sie die Definition des hyper Maschinenbedieners, wo die Startwerte für die Hinzufügung und Multiplikation auch getrennt angegeben werden.

Tische von Werten

Computerwissenschaft

Computerwissenschaft kann in Bezug auf einen unendlichen Tisch neu formuliert werden. Wir legen die Zahlen in die Spitzenreihe, und füllen die linke Säule mit Werten 2. Um eine Zahl im Tisch zu bestimmen, nehmen Sie die Zahl sofort nach links, dann schlagen Sie die erforderliche Zahl in der vorherigen Reihe an der Position nach, die durch die gerade genommene Zahl gegeben ist.

Der Tisch ist dasselbe als diese der Funktion von Ackermann, abgesehen von einer Verschiebung in und, und eine Hinzufügung von 3 zu allen Werten.

Computerwissenschaft

Wir legen die Zahlen in die Spitzenreihe, und füllen die linke Säule mit Werten 3. Um eine Zahl im Tisch zu bestimmen, nehmen Sie die Zahl sofort nach links, dann schlagen Sie die erforderliche Zahl in der vorherigen Reihe an der Position nach, die durch die gerade genommene Zahl gegeben ist.

Computerwissenschaft

Wir legen die Zahlen in die Spitzenreihe, und füllen die linke Säule mit Werten 10. Um eine Zahl im Tisch zu bestimmen, nehmen Sie die Zahl sofort nach links, dann schlagen Sie die erforderliche Zahl in der vorherigen Reihe an der Position nach, die durch die gerade genommene Zahl gegeben ist.

Bemerken Sie, dass für 2  n  9 die numerische Ordnung der Zahlen die lexikografische Ordnung mit der M als die am meisten bedeutende Anzahl ist, so für die Zahlen dieser 8 Säulen ist die numerische Ordnung einfach Linie-für-Linie-. Dasselbe bewirbt sich um die Zahlen in den 97 Säulen mit 3  n  99, und wenn wir von der M = 1 sogar für 3  n  9,999,999,999 anfangen.

Zählen-Systeme auf der Hyperarbeitsfolge gestützt

R. L. Goodstein, mit einem System der von Pfeilen von Knuth verschiedenen Notation, hat die Folge von Hypermaschinenbedienern verwendet, die hier angezeigt sind durch, Systeme des Zählens für die natürlichen Zahlen zu schaffen. Lassende Exponenten zeigen die jeweiligen Hypermaschinenbediener, die so genannte ganze erbliche Darstellung der ganzen Zahl n am Niveau k an und stützen b, kann wie folgt mit nur die ersten k Hypermaschinenbediener und mit als Ziffern nur 0, 1..., b-1 ausgedrückt werden:

• Für 0  n  b-1 wird n einfach durch die entsprechende Ziffer vertreten.
• Für n> b-1 wird die Darstellung von n rekursiv gefunden, zuerst n in der Form vertretend

:

:where x..., x sind die größten ganzen Zahlen, die (der Reihe nach) befriedigen

::

:...

:.

:Any x, b-1 zu weit gehend, wird dann auf dieselbe Weise wiederausgedrückt, und so weiter dieses Verfahren wiederholend, bis die resultierende Form nur die Ziffern 0, 1..., b-1 enthält.

Der Rest dieser Abteilung, wird aber nicht Exponenten verwenden, um die Hypermaschinenbediener anzuzeigen.

Unnötige Parenthesen können durch das Geben Maschinenbedienern des höheren Niveaus höherer Priorität in der Ordnung der Einschätzung vermieden werden; so,

Darstellungen des Niveaus 1 haben die Form, mit X auch dieser Form;

Darstellungen des Niveaus 2 haben die Form, mit X, Y auch dieser Form;

Darstellungen des Niveaus 3 haben die Form, mit X, Y, Z auch dieser Form;

Darstellungen des Niveaus 4 haben die Form, mit X, Y, Z, T auch dieser Form;

und so weiter.

Die Darstellungen können durch das Auslassen irgendwelcher Beispiele usw. abgekürzt werden; zum Beispiel, die Basis des Niveaus 3, die 2 Darstellung der Nummer 6 ist, der dazu abkürzt.

Beispiele:

Die einzigartige Basis 2 Darstellungen der Nummer 266, an Niveaus 1, 2, 3, 4, und 5 ist wie folgt:

:::::.

Siehe auch

• Primitiver recursion
• Maschinenbediener von Hyper
• Beschäftigter Biber
• Die Bar-Notation des Messerschmieds
• Extreme Exponentialfunktion
• Tetration

Links

• Robert Munafo, große Anzahl