Knuth's Up-arrow Notation

Website Links For Notation

Information About Knuth's Up-arrow Notation

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME
	MORE SHOPPING...

INTRODUCTION Multiplication by a Natural Number can be defined as iterated Addition : :$$ \begin{matrix} a b & = & \underbrace{a_{}+a+\dots+a} \ & & b\mbox{ copies of }a \end{matrix} and Exponentiation for a natural power $b$ can be defined as iterated multiplication: :$$ \begin{matrix} a\uparrow b= a^b = & \underbrace{a_{} imes a imes\dots imes a}\ & b\mbox{ copies of }a \end{matrix} which inspired Knuth to define a 'double arrow' Operator for iterated exponentiation or Tetration : :$$ \begin{matrix} a\uparrow\uparrow b & = {\ ^{b}a} = & \underbrace{a_{}^{a^}}}} & = & \underbrace{a_{}\uparrow a\uparrow\dots\uparrow a} \ & & b\mbox{ copies of }a & & b\mbox{ copies of }a \end{matrix} . Here and below evaluation is to take place from right to left (as such the operation is Right-associative ): According to this definition, :$3\backslash uparrow\backslash uparrow2=3^3=27\backslash ,\backslash !$ :$3\backslash uparrow\backslash uparrow3=3^\{3^3\}=3^\{27\}=7625597484987\backslash ,\backslash !$ :$3\backslash uparrow\backslash uparrow4=3^\{3^\{3^3\}\}=3^\{7625597484987\}\backslash ,\backslash !$ (just writing out this number in expanded form would fill a dozen moderately large hard drivesSpecifically bits, or about 1.37 TB) :$3\backslash uparrow\backslash uparrow5=3^\{3^\{3^\{3^3\}\}\}\; =\; 3^\{3^\{7625597484987\}\}\backslash ,\backslash !$ :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 'quad arrow' operator: :$$ \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 $n$-arrow operator expands into a series of ($n\; -\; 1$)-arrow operators. Symbolically, :$$ \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{ copies of }a \end{matrix} Examples: $3\backslash uparrow\backslash uparrow\backslash uparrow2=3\backslash uparrow\backslash uparrow3=3^\{3^3\}=3^\{27\}=7,625,597,484,987\backslash ,\backslash !$ $$ \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} NOTATION In expressions such as $a^b$, the notation for exponentiation is usually to write the exponent $b$ as a superscript to the base number $a$. But many environments — such as Programming Language s and plain-text E-mail — do not support such two-dimensional layout. People have adopted the linear notation $a\; \backslash uparrow\; b$ for such environments; the up-arrow suggests 'raising to the power of'. If the character set doesn't contain an up arrow, the Caret ^ is used instead. The superscript notation $a^b$ doesn't lend itself well for generalization, which explains why Knuth chose to work from the inline notation $a\; \backslash uparrow\; b$ instead. --- is a common alternative to $\backslash uparrow$ for discussion in this context, using the same principle of two symbols meaning repetition of that operator. It is possible that ''' -''' could be equivalent to $\backslash uparrow\backslash uparrow$, but this usage is uncommon. Writing out up-arrow notation in terms of powers Attempting to write $a\; \backslash uparrow\; \backslash uparrow\; b$ using the familiar superscript notation gives a power tower. With ''b'' too large to write ''b'' numbers ''a'', this requires using dots and a brace with the number ''b'' next to it, indicating the height of the power tower. $a\; \backslash uparrow\; \backslash uparrow\; \backslash uparrow\; b$ requires a row of such power towers, separated by braces: there are ''b'' power towers, including the last with height 1, hence simply the number ''a''. If ''b'' is too large to write all these power towers, we use dots to indicate a row of them, and for the number of power towers a "cross-brace" (the number of braces is one less). $a\; \backslash uparrow\; \backslash uparrow\; \backslash uparrow\; \backslash uparrow\; b$ requires a row of such rows of power towers; there are ''b'' rows of power towers, including the last, which consists of only one "power tower" of height 1, so is simply the number ''a''. If ''b'' is too large to write all these rows, we use a "cross-cross-brace" with this number ''b'' next to it (the number of cross-braces is one less). And so on. Since the power notation is in direction "/", the braces are too. A row of them could be written in perpendicular direction "\", and the cross-brace too. A row of cross-braces could then extend in the direction "/", with a cross-cross-brace too, etc. Example: For 4$\backslash uparrow\backslash uparrow\backslash uparrow$6 there are six power towers, including the last with height 1, hence simply the number 4; writing out the fifth power tower we have only five: :$\backslash begin\{matrix\}\; \backslash underbrace\{\backslash begin\{matrix\}\; \backslash underbrace\{4^\{4^\{4^\{.^\{.^\{.\{4\}\}\}\}\}\}\}\; \backslash \; \backslash underbrace\{4^\{4^\{4^\{.^\{.^\{.\{4\}\}\}\}\}\}\}\; \backslash \; \backslash underbrace\{4^\{4^\{4^\{.^\{.^\{.\{4\}\}\}\}\}\}\}\; \backslash \; \{4^\{4^\{4^\{.^\{.^\{.\{4\}\}\}\}\}\}\}\; \backslash end\{matrix\}\}\; \backslash \; \{4^\{4^\{4^\{4\}\}\}\}\; \backslash end\{matrix\}$ Using the left-superscript notation for tetration we have one "level of braces" less: $a\; \backslash uparrow\; \backslash uparrow\; \backslash uparrow\; b$ requires a "tetration tower" in the direction "\", and a brace with the number ''b'' next to it, indicating the height of the tetration tower. $a\; \backslash uparrow\; \backslash uparrow\; \backslash uparrow\; \backslash uparrow\; b$ requires a row of such tetration towers, separated by braces: there are ''b'' tetration towers, including the last with height 1, hence simply the number ''a''. If ''b'' is too large to write all these tetration towers, we use a "cross-brace" with this number ''b'' next to it. And so on. Examples: The previous example becomes :$^\{^\{^\{^\{^\{4\}4\}4\}4\}4\}4$ For the fourth Ackermann number $4\; \backslash uparrow\; \backslash uparrow\; \backslash uparrow\; \backslash uparrow\; 4$ there are four tetration towers, including the last with height 1, hence simply the number 4; writing out the third tetration tower we have only three: :$\backslash begin\{matrix\}\; \backslash underbrace\{\backslash begin\{matrix\}\; \backslash underbrace\{^\{^\{^\{^\{^\{^\{^\{4\}.\}.\}.\}4\}4\}4\}4\}\; \backslash \; ^\{^\{^\{^\{^\{^\{^\{4\}.\}.\}.\}4\}4\}4\}4\; \backslash end\{matrix\}\}\; \backslash \; ^\{^\{^\{^4\}4\}4\}4\; \backslash end\{matrix\}$ GENERALIZATIONS Some numbers are so large that multiple arrows of Knuth's up-arrow notation become too cumbersome; then an $n$-arrow operator $\backslash uparrow^n$ is useful (and also for descriptions with a variable number of arrows), or equivalently, Hyper Operator s. Some numbers are so large that even that notation is not sufficient. Graham's Number is an example. The Conway Chained Arrow Notation can then be used: a chain of three elements is equivalent with the other notations, but a chain of four or more is even more powerful. :$$ \begin{matrix} a\uparrow^n b & = & \mbox{hyper}(a,n+2,b) & = & a o b o n \ \mbox{(Knuth)} & & & & \mbox{(Conway)} \end{matrix} It is generally suggested that Knuth's arrow should be used for relatively smaller magnitude numbers, and the chained arrow or hyper operators for larger ones. DEFINITION The up-arrow notation is formally defined by :$$ a\uparrow^n b= \left\{ \begin{matrix} a^b, & \mbox{if }n=1; \ 1, & \mbox{if }b=0; \ a\uparrow^{n-1}(a\uparrow^n(b-1)), & \mbox{otherwise} \end{matrix} ight. for all integers $a,\; b,\; n$ with $b\; \backslash ge\; 0,\; n\; \backslash ge\; 1$. All up-arrow operators (including normal exponentiation, $a\; \backslash uparrow\; b$) are Right Associative , i.e. evaluation is to take place from right to left in an expression that contains two or more such operators. For example, $a\; \backslash uparrow\; b\; \backslash uparrow\; c\; =\; a\; \backslash uparrow\; (b\; \backslash uparrow\; c)$, not $(a\; \backslash uparrow\; b)\; \backslash uparrow\; c$; for example $3\backslash uparrow\backslash uparrow\; 3=3^\{3^3\}$ is $3^\{(3^3)\}=3^\{27\}=7625597484987$ not $\backslash left(3^3\; ight)^3=27^3=19683.$ There is good reason for the choice of this right-to-left order of evaluation. If we used left-to-right evaluation, then $a\; \backslash uparrow\backslash uparrow\; b$ would equal $a\; \backslash uparrow\; (a\; \backslash uparrow\; (b\; -\; 1))$, so that $\backslash uparrow\backslash uparrow$ would not be an essentially new operation. Right associativity is also natural because we can rewrite the iterated arrow expression $a\backslash uparrow^n\backslash cdots\backslash uparrow^na$ that appears in the expansion of $a\; \backslash uparrow^\{n\; +\; 1\}b$ as $a\backslash uparrow^n\backslash cdots\backslash uparrow^na\backslash uparrow^n1$, so that all the $a$s appear as left operands of arrow operators. This is significant since the arrow operators are not Commutative . Writing $(a\backslash uparrow\; ^m)^b$ for the ''b''th Functional Power of the function $f(n)=a\backslash uparrow\; ^m\; n$ we have $a\backslash uparrow\; ^n\; b\; =\; (a\backslash uparrow\; ^\{n-1\})^b\; 1$. The definition could be extrapolated one step, starting with $a\backslash uparrow^n\; b=\; ab$ if ''n'' = 0, because exponentiation is repeated multiplication starting with 1. Extrapolating one step more, writing multiplication as repeated addition, is not as straightforward because multiplication is repeated addition starting with 0 instead of 1. "Extrapolating" again one step more, writing addition of ''n'' as repeated addition of 1, requires starting with the number ''a''. Compare the , where the starting values for addition and multiplication are also separately specified. TABLES OF VALUES Computing $2\backslash uparrow^m\; n$ can be restated in terms of an infinite table. We place the numbers 2 $n$ in the top row, and fill the left column with values 2. To determine a number in the table, take the number immediately to the left, then look up the required number in the previous row, at the position given by the number just taken. 65536\mbox{ copies of }2 \end{matrix}\approx (10\uparrow)^{65531}(6.0 imes 10^{19,728})

65536\mbox{ copies of }2

{ Class "wikitable"

7,625,597,484,987\mbox{ copies of }3

{ Class "wikitable"

10\mbox{ copies of }10

Review our Terms of Service. © Copyright 2003-2009. Information About, Where you can have ALL your shopping needs met without unwanted poppups and clutter. If you have any comments, please write to info@informationdelight.info.