Jump to content
 







Main menu
   


Navigation  



Main page
Contents
Current events
Random article
About Wikipedia
Contact us
Donate
 




Contribute  



Help
Learn to edit
Community portal
Recent changes
Upload file
 








Search  

































Create account

Log in
 









Create account
 Log in
 




Pages for logged out editors learn more  



Contributions
Talk
 



















Contents

   



(Top)
 


1 Introduction  





2 Notation  



2.1  Writing out up-arrow notation in terms of powers  



2.1.1  Using tetration  









3 Generalizations  





4 Definition  





5 Tables of values  



5.1  Computing 0n b  





5.2  Computing 2n b  





5.3  Computing 3n b  





5.4  Computing 4n b  





5.5  Computing 10n b  







6 See also  





7 Notes  





8 References  





9 External links  














Knuth's up-arrow notation






Català
Čeština
Deutsch
Español
Esperanto
Français

Bahasa Indonesia
Italiano
Bahasa Melayu
Nederlands

Norsk bokmål
Polski
Português
Русский
Simple English
Slovenščina
Српски / srpski
Suomi
Svenska

Türkçe
Українська
Tiếng Vit

 

Edit links
 









Article
Talk
 

















Read
Edit
View history
 








Tools
   


Actions  



Read
Edit
View history
 




General  



What links here
Related changes
Upload file
Special pages
Permanent link
Page information
Cite this page
Get shortened URL
Download QR code
Wikidata item
 




Print/export  



Download as PDF
Printable version
 
















Appearance
   

 






From Wikipedia, the free encyclopedia
 


Inmathematics, Knuth's up-arrow notation is a method of notation for very large integers, introduced by Donald Knuth in 1976.[1]

In his 1947 paper,[2] 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 operationsofaddition (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 . Knuth's up-arrow notation is another. For example:

The general definition of the up-arrow notation is as follows (for ): Here, stands for n arrows, so for example The square brackets are another notation for hyperoperations.

Introduction[edit]

The hyperoperations naturally extend the arithmetic 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 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,

etc.

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 -arrow operator expands into a right-associative series of ()-arrow operators. Symbolically,

Examples:

Notation[edit]

In expressions such as , the notation for exponentiation is usually to write the exponent as a superscript to the base number . But many environments — such as programming languages and plain-text e-mail — do not support superscript typesetting. People have adopted the linear notation 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 doesn't lend itself well to generalization, which explains why Knuth chose to work from the inline notation instead.

is a shorter alternative notation for n uparrows. Thus .

Writing out up-arrow notation in terms of powers[edit]

Attempting to write using the familiar superscript notation gives a power tower.

For example:

Ifb 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, 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, 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 as iterated exponentiation of iterated exponentiation for any a, n and b (although it clearly becomes rather cumbersome).

Using tetration[edit]

The Rudy Rucker notation 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 could be represented as:

Generalizations[edit]

Some numbers are so large that multiple arrows of Knuth's up-arrow notation become too cumbersome; then an n-arrow operator 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.

= , Since = = , Thus the result comes out with

= or (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 . For the standard fast-growing hierarchy using , already exhibits exponential growth, is comparable to tetrational growth and is upper-bounded by a function involving the first four hyperoperators;. Then, is comparable to the Ackermann function, is already beyond the reach of indexed arrows but can be used to approximate Graham's number, and 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 exist 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[edit]

Without reference to hyperoperation the up-arrow operators can be formally defined by

for all integers with [nb 1].

This definition uses exponentiation as the base case, and tetration 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 as the base case and iterate from there. Then exponentiation becomes repeated multiplication. The formal definition would be

for all integers with .

Note, however, that Knuth did not define the "nil-arrow" (). 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, is understood to be , instead of . If ambiguity is not an issue parentheses are sometimes dropped.

Tables of values[edit]

Computing 0↑n b[edit]

Computing results in

0, when n = 0  [nb 2]
1, when n = 1 and b = 0   [nb 1][nb 3]
0, when n = 1 and b > 0   [nb 1][nb 3]
1, when n > 1 and b is even (including 0)
0, when n > 1 and b is odd

Computing 2↑n b[edit]

Computing can be restated in terms of an infinite table. We place the numbers 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.

Values of = = = 2 → b → n

b

1 2 3 4 5 6 formula
1 2 4 8 16 32 64
2 2 4 16 65536
3 2 4 65536
4 2 4

The table is the same as that of the Ackermann function, except for a shift in and , and an addition of 3 to all values.

Computing 3↑n b[edit]

We place the numbers 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.

Values of = = = 3 → b → n

b

1 2 3 4 5 formula
1 3 9 27 81 243
2 3 27 7,625,597,484,987
3 3 7,625,597,484,987
4 3

Computing 4↑n b[edit]

We place the numbers 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.

Values of = = = 4 → b → n

b

1 2 3 4 5 formula
1 4 16 64 256 1024
2 4 256
3 4
4 4

Computing 10↑n b[edit]

We place the numbers 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.

Values of = = = 10 → b → n

b

1 2 3 4 5 formula
1 10 100 1,000 10,000 100,000
2 10 10,000,000,000
3 10
4 10

For 2 ≤ b ≤ 9 the numerical order of the numbers 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.

See also[edit]

Notes[edit]

  1. ^ a b c For more details, see Powers of zero.
  • ^ Keep in mind that Knuth did not define the operator .
  • ^ a b For more details, see Zero to the power of zero.
  • References[edit]

    1. ^ Knuth, Donald E. (1976). "Mathematics and Computer Science: Coping with Finiteness". Science. 194 (4271): 1235–1242. Bibcode:1976Sci...194.1235K. doi:10.1126/science.194.4271.1235. PMID 17797067. S2CID 1690489.
  • ^ R. L. Goodstein (Dec 1947). "Transfinite Ordinals in Recursive Number Theory". Journal of Symbolic Logic. 12 (4): 123–129. doi:10.2307/2266486. JSTOR 2266486. S2CID 1318943.
  • External links[edit]


    Retrieved from "https://en.wikipedia.org/w/index.php?title=Knuth%27s_up-arrow_notation&oldid=1223533066"

    Categories: 
    Mathematical notation
    Large numbers
    Donald Knuth
    1976 introductions
    Hidden categories: 
    Articles with short description
    Short description matches Wikidata
     



    This page was last edited on 12 May 2024, at 19:42 (UTC).

    Text is available under the Creative Commons Attribution-ShareAlike License 4.0; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization.



    Privacy policy

    About Wikipedia

    Disclaimers

    Contact Wikipedia

    Code of Conduct

    Developers

    Statistics

    Cookie statement

    Mobile view



    Wikimedia Foundation
    Powered by MediaWiki