Knuth's up-arrow notation
In mathematics, Knuth's up-arrow notation is a method of notation for very large integers, introduced by Donald Knuth in 1976. In his 1947 paper, R. L. Goodstein introduced the specific sequence of operations that are now called "hyperoperations". Goodstein also suggested the Greek names tetration, pentation, etc., for the extended operations beyond exponentiation. The sequence starts with a unary operation (the successor function with "n" = 0), and continues with the binary operations of addition ("n" = 1), multiplication ("n" = 2), exponentiation ("n" = 3), tetration ("n" = 4), pentation ("n" =  5), etc. Various notations have been used to represent hyperoperations. One such notation is formula_1. Another notation is formula_2, an infix notation which is convenient for ASCII. The notation formula_2 is known as 'square bracket notation'. Knuth's up-arrow notation formula_4 is an alternative notation. It is obtained by replacing formula_5 in the square bracket notation by formula_6 arrows. For example: The general definition of the up-arrow notation is as follows (for formula_13): formula_14 Here, formula_15 stands for "n" arrows, so for example formula_16 Introduction. The hyperoperations naturally extend the arithmetical operations of addition and multiplication as follows . Addition by a natural number is defined as iterated incrementation: Multiplication by a natural number is defined as iterated addition: For example, Exponentiation for a natural power formula_20 is defined as iterated multiplication, which Knuth denoted by a single up-arrow: For example, Tetration is defined as iterated exponentiation, which Knuth denoted by a “double arrow”: For example, Expressions are evaluated from right to left, as the operators are defined to be right-associative. According to this definition, This already leads to some fairly large numbers, but the hyperoperator sequence does not stop here. Pentation, defined as iterated tetration, is  represented by the “triple arrow”: Hexation, defined as iterated pentation, is represented by the “quadruple arrow”: and so on. The general rule is that an formula_31-arrow operator expands into a right-associative series of (formula_32)-arrow operators. Symbolically, Examples: Notation. In expressions such as formula_36, the notation for exponentiation is usually to write the exponent formula_20 as a superscript to the base number formula_38. But many environments — such as programming languages and plain-text e-mail — do not support superscript typesetting. People have adopted the linear notation formula_39 for such environments; the up-arrow suggests 'raising to the power of '. If the character set does not contain an up arrow, the caret (^) is used instead. The superscript notation formula_36 doesn't lend itself well to generalization, which explains why Knuth chose to work from the inline notation formula_39 instead. formula_42 is a shorter alternative notation for n uparrows. Thus formula_43. Knuth's arrows have become quite popular, maybe because formula_15 is a stronger logo than for instance formula_5. Writing out up-arrow notation in terms of powers. Attempting to write formula_46 using the familiar superscript notation gives a power tower. If "b" is a variable (or is too large ), the power tower might be written using dots and a note indicating the height of the tower. Continuing with this notation, formula_49 could be written with a stack of such power towers, each describing the size of the one above it. Again, if "b" is a variable or is too large, the stack might be written using dots and a note indicating its height. Furthermore, formula_52 might be written using several columns of such stacks of power towers, each column describing the number of power towers in the stack to its left: And more generally: This might be carried out  indefinitely to represent formula_42 as iterated exponentiation of iterated exponentiation for any "a", "n" and "b" (although it clearly becomes rather cumbersome). Using tetration. The Rudy Rucker notation formula_56 for tetration allows us to make these diagrams slightly simpler while still employing a geometric representation (we could call these "tetration towers"). Finally, as an example, the fourth Ackermann number formula_60 could be represented as: Generalizations. Some numbers are so large that multiple arrows of Knuth's up-arrow notation become too cumbersome; then an "n"-arrow operator formula_15 is useful (and also for descriptions with a variable number of arrows), or  equivalently, hyper operators. Some numbers are so large that even that notation is not sufficient. 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. formula_64 = formula_65, Since formula_64 = formula_67 = formula_68, Thus the result comes out with formula_65 formula_70 = formula_71 or formula_72 (Petillion) Even faster-growing functions can be categorized using an ordinal analysis called the fast-growing hierarchy. The fast-growing hierarchy uses successive function iteration and diagonalization to systematically create faster-growing functions  from some base function formula_73. For the standard fast-growing hierarchy using formula_74, formula_75 already exhibits exponential growth, formula_76 is comparable to tetrational growth and is upper-bounded by a function involving the first four hyperoperators;. Then, formula_77 is comparable to the Ackermann function, formula_78 is already beyond the reach of indexed arrows but can be used to approximate Graham's number, and formula_79 is comparable to arbitrarily-long Conway chained arrow notation. These functions are all computable. Even faster computable functions, such as the Goodstein sequence and the TREE sequence require the usage of large ordinals, may occur in  certain combinatorical and proof-theoretic contexts. There exists functions which grow uncomputably fast, such as the Busy Beaver, whose very nature will be completely out of reach from any up-arrow, or even any ordinal-based analysis. Definition. Without reference to hyperoperation the up-arrow operators can be formally defined by for all integers formula_81 with formula_13. This definition uses exponentiation formula_83 as the base case, and tetration formula_84 as repeated exponentiation. This is equivalent to the hyperoperation sequence except it omits the three more basic operations of succession, addition and multiplication. One can alternatively choose multiplication formula_85 as the  base case and iterate from there. Then exponentiation becomes repeated multiplication. The formal definition would be for all integers formula_81 with formula_88. Note, however, that Knuth did not define the "nil-arrow" (formula_89). One could extend the notation to negative indices (n ≥ -2) in such a way as to agree with the entire hyperoperation sequence, except for the lag in the indexing: The up-arrow operation is a right-associative operation, that is, formula_91 is understood to be formula_92, instead of formula_93. If ambiguity is not an issue parentheses are sometimes dropped. Tables of values. Computing 0↑ "b". Computing  formula_94 results in Computing 2↑ "b". Computing formula_95 can be restated in terms of an infinite table. We place the numbers formula_96 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. The table is the same as that of the Ackermann function, except for a shift in formula_31 and formula_20, and an addition of 3 to all values. Computing 3↑ "b". We place the  numbers formula_99 in the top row, and fill the left column with values 3. 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. Computing 4↑ "b". We place the numbers formula_100 in the top row, and fill the left column with values 4. 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 . Computing 10↑ "b". We place the numbers formula_101 in the top row, and fill the left column with values 10. 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. For 2 ≤ "b" ≤ 9 the numerical order of the numbers formula_102 is the lexicographical order with "n" as the most significant number, so for the numbers of these 8 columns the numerical order is simply line-by-line. The same applies for the numbers in  the 97 columns with 3 ≤ "b" ≤ 99, and if we start from "n" = 1 even for 3 ≤ "b" ≤ 9,999,999,999.