Knuth’s up-arrow notation
E94986
Knuth’s up-arrow notation is a mathematical notation introduced by Donald Knuth to concisely represent very large integers using iterated exponentiation and its higher-order generalizations.
Observed surface forms (1)
| Surface form | Occurrences |
|---|---|
| Knuth up-arrow notation | 1 |
Statements (50)
| Predicate | Object |
|---|---|
| instanceOf |
hyperoperation notation
ⓘ
mathematical notation ⓘ |
| alternativeTo |
Conway chained arrow notation for some ranges
ⓘ
power tower notation ⓘ |
| basedOn | iterated exponentiation ⓘ |
| clarifies | hierarchy of operations beyond exponentiation ⓘ |
| convention | operations are right-associative in b ⓘ |
| creator | Donald Knuth NERFINISHED ⓘ |
| defines |
a ↑ b = a^b (ordinary exponentiation)
ⓘ
a ↑^n b recursively for n ≥ 1 ⓘ a ↑↑ b = a tetrated to height b ⓘ a ↑↑↑ b = a pentated to height b ⓘ |
| domain |
a is a positive integer
ⓘ
b is a nonnegative integer ⓘ |
| example |
2 ↑↑ 5 = 2^(2^(2^(2^2)))
ⓘ
2 ↑↑↑ 3 = 2 ↑↑ (2 ↑↑ 2) ⓘ 3 ↑ 3 = 27 ⓘ 3 ↑↑ 3 = 3^(3^3) = 3^27 ⓘ |
| field |
computational complexity theory
ⓘ
mathematics ⓘ number theory ⓘ |
| generalizes |
exponentiation
ⓘ
tetration ⓘ |
| growthRate | grows faster than any fixed-height tower of exponentials ⓘ |
| hasParameter |
arrow level n (number of up-arrows)
ⓘ
base a ⓘ height or iteration count b ⓘ |
| influenced | Conway chained arrow notation NERFINISHED ⓘ |
| introducedBy | Donald Knuth NERFINISHED ⓘ |
| introducedIn | 20th century ⓘ |
| introducedInContextOf | analysis of algorithms ⓘ |
| language | symbolic mathematics ⓘ |
| notationSymbol |
↑
ⓘ
↑^n (n up-arrows) ⓘ ↑↑ ⓘ ↑↑↑ ⓘ |
| notationType | prefix binary operation on integers ⓘ |
| partOf | hyperoperation sequence ⓘ |
| purpose | to represent very large integers concisely ⓘ |
| recurrenceRule |
a ↑^n (b+1) = a ↑^{n-1} (a ↑^n b) for n ≥ 2, b ≥ 1
ⓘ
a ↑^n 1 = a for n ≥ 1 ⓘ |
| relatedTo |
Ackermann function
ⓘ
Conway chained arrow notation ⓘ fast-growing hierarchy ⓘ hyperoperations ⓘ tetration ⓘ |
| usedFor |
defining extremely fast-growing functions
ⓘ
describing growth rates beyond primitive recursive functions ⓘ expressing large bounds in proof theory ⓘ expressing large numbers in combinatorics ⓘ |
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.
this entity surface form:
Knuth up-arrow notation