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:

    “Such is oftenest the young man’s introduction to the forest, and the most original part of himself. He goes thither at first as a hunter and fisher, until at last, if he has the seeds of a better life in him, he distinguishes his proper objects, as a poet or naturalist it may be, and leaves the gun and fish-pole behind. The mass of men are still and always young in this respect.”
    —Henry David Thoreau (1817–1862)

    “Do you suppose I could buy back my introduction to you?”
    —S.J. Perelman, U.S. screenwriter, Arthur Sheekman, Will Johnstone, and Norman Z. McLeod. Groucho Marx, Monkey Business, a wisecrack made to his fellow stowaway Chico Marx (1931)

    “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)