Knuth's Up-arrow Notation - Introduction

Introduction

The ordinary arithmetical operations of addition, multiplication and exponentiation are naturally extended into a sequence of hyperoperations as follows.

Multiplication by a natural number is defined as iterated addition:

\begin{matrix} a\times b & = & \underbrace{a+a+\dots+a} \\ & & b\mbox{ copies of }a \end{matrix}

For example,

\begin{matrix} 4\times 3 & = & \underbrace{4+4+4} & = & 12\\ & & 3\mbox{ copies of }4 \end{matrix}

Exponentiation for a natural power is defined as iterated multiplication, which Knuth denoted by a single up-arrow:

\begin{matrix} a\uparrow b= a^b = & \underbrace{a\times a\times\dots\times a}\\ & b\mbox{ copies of }a \end{matrix}

For example,

\begin{matrix} 4\uparrow 3= 4^3 = & \underbrace{4\times 4\times 4} & = & 64\\ & 3\mbox{ copies of }4 \end{matrix}

To extend the sequence of operations beyond exponentiation, Knuth defined a “double arrow” operator to denote iterated exponentiation (tetration):

\begin{matrix} a\uparrow\uparrow b & = {\ ^{b}a} = & \underbrace{a^{a^{{}^{.\,^{.\,^{.\,^a}}}}}} & = & \underbrace{a\uparrow (a\uparrow(\dots\uparrow a))} \\ & & b\mbox{ copies of }a & & b\mbox{ copies of }a \end{matrix}

For example,

\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{ copies of }4 & & 3\mbox{ copies of }4 \end{matrix}

Here and below evaluation is to take place from right to left, as Knuth's arrow operators (just like exponentiation) are defined to be right-associative.

According to this definition,

etc.

This already leads to some fairly large numbers, but Knuth extended the notation. He went on to define a “triple arrow” operator for iterated application of the “double arrow” operator (also known as pentation):

\begin{matrix} a\uparrow\uparrow\uparrow b= & \underbrace{a_{}\uparrow\uparrow (a\uparrow\uparrow(\dots\uparrow\uparrow a))}\\ & b\mbox{ copies of }a \end{matrix}

followed by a 'quadruple arrow' operator (also known as 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{ copies of }a \end{matrix}

and so on. The general rule is that an -arrow operator expands into a right-associative series of -arrow operators. Symbolically,

\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{ copies of }a} \end{matrix}

Examples:

\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{ copies of }3 \end{matrix} \begin{matrix} = & \underbrace{3_{}\uparrow 3\uparrow\dots\uparrow 3} \\ & \mbox{7,625,597,484,987 copies of 3} \end{matrix}

The notation is commonly used to denote with n arrows.

Read more about this topic:  Knuth's Up-arrow Notation

Famous quotes containing the word introduction:

    “The role of the stepmother is the most difficult of all, because you can’t ever just be. You’re constantly being tested—by the children, the neighbors, your husband, the relatives, old friends who knew the children’s parents in their first marriage, and by yourself.”
    —Anonymous Stepparent. Making It as a Stepparent, by Claire Berman, introduction (1980, repr. 1986)

    “We used chamber-pots a good deal.... My mother ... loved to repeat: “When did the queen reign over China?” This whimsical and harmless scatological pun was my first introduction to the wonderful world of verbal transformations, and also a first perception that a joke need not be funny to give pleasure.”
    —Angela Carter (1940–1992)

    “My objection to Liberalism is this—that it is the introduction into the practical business of life of the highest kind—namely, politics—of philosophical ideas instead of political principles.”
    —Benjamin Disraeli (1804–1881)