{
  "id": "enwiki-001375889129",
  "slug": "hyperoperation",
  "title": "Hyperoperation",
  "qid": "",
  "lead": "In mathematics, the hyperoperation sequence is an infinite sequence of arithmetic operations (called hyperoperations in this context) that starts with a unary operation (the successor function with ). The sequence continues with the binary operations of addition ( ), multiplication ( ), and exponentiation ( ). After that, the sequence proceeds with further binary operations extending beyond exponentiation, using right-associativity. For the operations beyond exponentiation, the -th member of this sequence is named by Reuben Goodstein after the Greek prefix of suffixed with -ation (such as tetration ( ), pentation ( ), hexation ( ), etc.) and can be written using arrows in Knuth's up-arrow notation. Each hyperoperation may be understood recursively in terms of the previous one by: a[n]b = \\underbrace{a[n-1](a[n-1](a[n-1](\\cdots a[n-1](a[n-1](a[n-1]a))\\cdots)))}_{\\displaystyle b \\mbox{ copies of } a},\\quad n \\ge 2 It may also be defined according to the recursion rule part of the definition, as in Knuth's up-arrow version of the Ackermann function: a[n]b = a[n-1]\\left(a[n]\\left(b - 1\\right)\\right),\\quad n \\ge 1 This can be used to easily show numbers much larger than those which scientific notation can, such as Skewes's number and googolplexplex (e.g.…",
  "body": "In mathematics, the hyperoperation sequence is an infinite sequence of arithmetic operations (called hyperoperations in this context) that starts with a unary operation (the successor function with ). The sequence continues with the binary operations of addition ( ), multiplication ( ), and exponentiation ( ). After that, the sequence proceeds with further binary operations extending beyond exponentiation, using right-associativity. For the operations beyond exponentiation, the -th member of this sequence is named by Reuben Goodstein after the Greek prefix of suffixed with -ation (such as tetration ( ), pentation ( ), hexation ( ), etc.) and can be written using arrows in Knuth's up-arrow notation. Each hyperoperation may be understood recursively in terms of the previous one by: a[n]b = \\underbrace{a[n-1](a[n-1](a[n-1](\\cdots a[n-1](a[n-1](a[n-1]a))\\cdots)))}_{\\displaystyle b \\mbox{ copies of } a},\\quad n \\ge 2 It may also be defined according to the recursion rule part of the definition, as in Knuth's up-arrow version of the Ackermann function: a[n]b = a[n-1]\\left(a[n]\\left(b - 1\\right)\\right),\\quad n \\ge 1 This can be used to easily show numbers much larger than those which scientific notation can, such as Skewes's number and googolplexplex (e.g. 50[50]50 is much larger than Skewes's number and googolplexplex), but there are some numbers which even they cannot easily show, such as Graham's number and TREE(3). This recursion rule is common to many variants of hyperoperations. H_n(a,b) = \\begin{cases} b + 1 & \\text{if } n = 0 \\\\ a & \\text{if } n = 1 \\text{ and } b = 0 \\\\ 0 & \\text{if } n = 2 \\text{ and } b = 0 \\\\ 1 & \\text{if } n \\ge 3 \\text{ and } b = 0 \\\\ H_{n-1}(a, H_n(a, b - 1)) & \\text{otherwise} \\end{cases}. For , this definition reproduces the basic arithmetic operations of successor (which is a unary operation), addition, multiplication, and exponentiation, respectively, as \\begin{align} H_0(a, b) &= b + 1, \\\\ H_1(a, b) &= a + b, \\\\ H_2(a, b) &= a \\times b, \\\\ H_3(a, b) &= a^{b} \\end{align} for all nonnegative integers and . The hyperoperations can thus be seen as an answer to the question \"what's next?\" in the sequence of functions that begins successor, addition, multiplication, exponentiation. Just as integer multiplication is defined as iterated addition and integer exponentiation is defined by iterated multiplication, the next hyperoperation, tetration, is defined by iterated exponentiation; for example, H_4(a, 3) = \\operatorname{tetration}(a, 3) = a^{a^a} is a power tower of three s, and H_4(a, 4) = \\operatorname{tetration}(a, 4) = a^{a^{a^a}} . Likewise the fifth hyperoperation pentation, is defined by iterated tetration, so that H_5(a, 3) = \\operatorname{tetration}(a, \\operatorname{tetration}(a, a)) . The parameters of the hyperoperation hierarchy are sometimes referred to by their analogous exponentiation term; so is the base, is the exponent (or hyperexponent), and is the rank (or grade). In general, H_n(a, b) may be read as \"the -th -ation of \", so that H_4(7,9) is read as \"the 9th tetration of 7\", and H_{123}(456,789) is read as \"the 789th 123-ation of 456\". An alternative way of writing hyperoperations is the compact notation a[n]b for H_n(a, b) . In this notation, exponentiation is denoted a[3]b = a^b , tetration is denoted a[4]b (so that a[4]3 = a^{a^a} , pentation is denoted a[5]b , and so on. Hyperoperations can also be expressed using Knuth's up-arrow notation. In this notation, a\\uparrow b represents the exponentiation function a^b , a\\uparrow \\uparrow b represents tetration, a \\uparrow \\uparrow \\uparrow b or a \\uparrow^{3}b represents the pentation a[5]b , and more generally H_n(a, b) = a \\uparrow^{n-2}b for n \\ge 0. Yet another alternative is Conway chained arrow notation. In this notation, one has H_n(a, b) = a[n]b = a \\rightarrow b \\rightarrow n - 2 , so that (for example) a[5]b = a\\rightarrow b\\rightarrow 3 . ==Special cases== , when , when 0, when 1, when and 0, when and 1, when and is even (including 0) 0, when and is odd , when 1, when 0, when 1, when , or , when 2, when , when , when , when 0, when , or , when , when , when 3, when 4, when , easily demonstrable recursively. In his 1947 paper, Reuben Goodstein introduced the specific sequence of operations that are now called hyperoperations, and also suggested the Greek names tetration, pentation, etc., for the extended operations beyond exponentiation (because they correspond to the indices 4, 5, etc.). As a three-argument function, e.g., G(n, a, b) = H_n(a, b) , the hyperoperation sequence as a whole is seen to be a version of the original Ackermann function \\phi(a, b, n) — recursive but not primitive recursive — as modified by Goodstein to incorporate the primitive successor function together with the other three basic operations of arithmetic (addition, multiplication, exponentiation), and to make a more seamless extension of these beyond exponentiation. The original three-argument Ackermann function \\phi uses the same recursion rule as does Goodstein's version of it (i.e., the hyperoperation sequence), but differs from it in two ways. First, \\phi(a, b, n) defines a sequence of operations starting from addition ( ) rather than the successor function, then multiplication ( ), exponentiation ( ), etc. Secondly, the initial conditions for \\phi result in \\phi(a, b, 3) = G(4,a,b+1) = a [4] (b + 1) , thus differing from the hyperoperations beyond exponentiation. The significance of the in the previous expression is that \\phi(a, b, 3) = a^{a^{\\cdot^{\\cdot^{\\cdot^a}}}} , where counts the number of operators (exponentiations), rather than counting the number of operands (\"a\"s) as does the in a [4] b , and so on for the higher-level operations. (See the Ackermann function article for details.) In 1928, Wilhelm Ackermann defined a 3-argument function \\phi(a, b, n) which gradually evolved into a 2-argument function known as the Ackermann function. The original Ackermann function \\phi was less similar to modern hyperoperations, because his initial conditions start with \\phi(a, 0, n) = a for all . Also he assigned addition to , multiplication to and exponentiation to , so the initial conditions produce very different operations for tetration and beyond. Another initial condition that has been used is A(0, b) = 2b + 1 (where the base is constant a = 2 ), due to Rózsa Péter, which does not form a hyperoperation hierarchy. Since then, many other authors have renewed interest in the application of hyperoperations to floating-point representation. (Since are all defined for .) While discussing tetration, Clenshaw et al. assumed the initial condition F_n(a, 0) = 0 , which makes yet another hyperoperation hierarchy. Just like in the previous variant, the fourth operation is very similar to tetration, but offset by one. \\begin{align} a + b &= (a + (b - 1)) + 1 \\\\ a \\cdot b &= (a \\cdot (b - 1)) + a \\\\ a^b &= \\left(a^{(b-1)}\\right) \\cdot a \\end{align} define (with ° or subscript) a_{(n)}b = \\left(a_{(n)}(b - 1)\\right)_{(n-1)} a with \\begin{align} a_{(1)} b &= a + b \\\\ a_{(2)} 0 &= 0 \\\\ a_{(n)} 1 &= a & \\text{for } n>2 \\\\ \\end{align} This was extended to ordinal numbers by Doner and Tarski. They have index 0 rather than index 1 for addition. They extend the formulas to also handle each ordinal with no immediate predecessor by replacing in the above with the supremum over all ordinals less than , and they treat similarly. We use Greek letters to indicate that these are ordinal numbers not simply counting numbers. \\begin{align} \\alpha O_0 \\beta &= \\alpha + \\beta \\\\ \\alpha O_\\nu \\beta &= \\sup\\limits_{\\delta With these definitions is addition, is multiplication, and is exponentiation. However, fails to form the \"power tower\" apparent with the corresponding (non-lower) hyperoperation. Instead, \\alpha O_3 (1 + \\beta) = \\alpha^{\\left(\\alpha^\\beta\\right)}. F_{n+1}(a, b) = \\exp(F_n(\\ln(a), \\ln(b))) which is symmetric in and , meaning all hyperoperations are commutative. This sequence does not contain exponentiation, and so does not form a hyperoperation hierarchy. ==Numeration systems based on the hyperoperation sequence== R. L. Goodstein used the sequence of hyperoperators to create systems of numeration for the nonnegative integers. The so-called complete hereditary representation of integer , at level and base , can be expressed as follows using only the first hyperoperators and using as digits only , together with the base itself: For , is represented simply by the corresponding digit. For , the representation of is found recursively, first representing in the form where are the largest integers satisfying (in turn) ... Any exceeding is then re-expressed in the same manner, and so on, repeating this procedure until the resulting form contains only the digits , together with the base . Unnecessary parentheses can be avoided by giving higher-level operators higher precedence in the order of evaluation; thus, level-1 representations have the form , with also of this form; level-2 representations have the form , with , also of this form; level-3 representations have the form , with , , also of this form; level-4 representations have the form , with , , , also of this form; and so on. In this type of base- hereditary representation, the base itself appears in the expressions, as well as \"digits\" from the set . This compares to ordinary base-2 representation when the latter is written out in terms of the base ; e.g., in ordinary base-2 notation, 6 = (110) 2 = 2 [3] 2 [2] 1 [1] 2 [3] 1 [2] 1 [1] 2 [3] 0 [2] 0, whereas the level-3 base-2 hereditary representation is 6 = 2 [3] (2 [3] 1 [2] 1 [1] 0) [2] 1 [1] (2 [3] 1 [2] 1 [1] 0). The hereditary representations can be abbreviated by omitting any instances of [1] 0, [2] 1, [3] 1, [4] 1, etc.; for example, the above level-3 base-2 representation of 6 abbreviates to 2 [3] 2 [1] 2. Examples: The unique base-2 representations of the number 266, at levels 1, 2, 3, 4, and 5 are as follows: Level 1: 266 = 2 [1] 2 [1] 2 [1] ... [1] 2 (with 133 2s) Level 2: 266 = 2 [2] (2 [2] (2 [2] (2 [2] 2 [2] 2 [2] 2 [2] 2 [1] 1)) [1] 1) Level 3: 266 = 2 [3] 2 [3] (2 [1] 1) [1] 2 [3] (2 [1] 1) [1] 2 Level 4: 266 = 2 [4] (2 [1] 1) [3] 2 [1] 2 [4] 2 [2] 2 [1] 2 Level 5: 266 = 2 [5] 2 [4] 2 [1] 2 [5] 2 [2] 2 [1] 2 ==Computation== The definitions of the hyperoperation sequence can naturally be transposed to term rewriting systems (TRS). ===TRS based on definition sub 1.1=== The basic definition of the hyperoperation sequence corresponds with the reduction rules \\begin{array}{lll} \\text{(r1)} & H(0,a,b) & \\rightarrow & S(b) \\\\ \\text{(r2)} & H(S(0),a,0) & \\rightarrow & a \\\\ \\text{(r3)} & H(S(S(0)),a,0) & \\rightarrow & 0 \\\\ \\text{(r4)} & H(S(S(S(n))),a,0) & \\rightarrow & S(0) \\\\ \\text{(r5)} & H(S(n),a,S(b)) & \\rightarrow & H(n,a,H(S(n),a,b)) \\end{array} To compute H_{n}(a, b) one can use a stack, which initially contains the elements \\langle n,a,b \\rangle . Then, repeatedly until no longer possible, three elements are popped and replaced according to the rules \\begin{array}{lllllllll} \\text{(r1)} & 0 &,& a &,& b & \\rightarrow & (b+1) \\\\ \\text{(r2)} & 1 &,& a &,& 0 & \\rightarrow & a \\\\ \\text{(r3)} & 2 &,& a &,& 0 & \\rightarrow & 0 \\\\ \\text{(r4)} & (n+3) &,& a &,& 0 & \\rightarrow & 1 \\\\ \\text{(r5)} & (n+1) &,& a &,& (b+1) & \\rightarrow & n &,& a &,& (n+1) &,& a &,& b \\end{array} Schematically, starting from \\langle n,a,b \\rangle : WHILE stackLength <> 1 { POP 3 elements; PUSH 1 or 5 elements according to the rules r1, r2, r3, r4, r5; } Example Compute H_2(2,2) \\rightarrow_{*} 4 . The reduction sequence is When implemented using a stack, on input \\langle 2,2,2 \\rangle ===TRS based on definition sub 1.2=== The definition using iteration leads to a different set of reduction rules \\begin{array}{lll} \\text{(r6)} & H(S(0),0,a,b) & \\rightarrow & S(b) \\\\ \\text{(r7)} & H(S(0),S(0),a,0) & \\rightarrow & a \\\\ \\text{(r8)} & H(S(0),S(S(0)),a,0) & \\rightarrow & 0 \\\\ \\text{(r9)} & H(S(0),S(S(S(n))),a,0) & \\rightarrow & S(0) \\\\ \\text{(r10)} & H(S(0),S(n),a,S(b)) & \\rightarrow & H(S(b),n,a,H(S(0),S(n),a,0)) \\\\ \\text{(r11)} & H(S(S(x)),n,a,b) & \\rightarrow & H(S(0),n,a,H(S(x),n,a,b)) \\end{array} As iteration is associative, instead of rule r11 one can define \\begin{array}{lll} \\text{(r12)} & H(S(S(x)),n,a,b) & \\rightarrow & H(S(x),n,a,H(S(0),n,a,b)) \\end{array} Like in the previous section the computation of H_n(a,b) = H^1_n(a,b) can be implemented using a stack. Initially the stack contains the four elements \\langle 1,n,a,b \\rangle . Then, until termination, four elements are popped and replaced according to the rules \\begin{array}{lllllllll} \\text{(r6)} & 1 &, 0 &, a &, b & \\rightarrow & (b+1) \\\\ \\text{(r7)} & 1 &, 1 &, a &, 0 & \\rightarrow & a \\\\ \\text{(r8)} & 1 &, 2 &, a &, 0 & \\rightarrow & 0 \\\\ \\text{(r9)} & 1 &, (n+3) &, a &, 0 & \\rightarrow & 1 \\\\ \\text{(r10)} & 1 &, (n+1) &, a &, (b+1) & \\rightarrow & (b+1) &, n &, a &, 1 &, (n+1) &, a &, 0 \\\\ \\text{(r11)} & (x+2) &, n &, a &, b & \\rightarrow & 1 &, n &, a &, (x+1) &, n &, a &, b \\end{array} Schematically, starting from \\langle 1,n,a,b \\rangle : WHILE stackLength <> 1 { POP 4 elements; PUSH 1 or 7 elements according to the rules r6, r7, r8, r9, r10, r11; } Example Compute H_3(0,3) \\rightarrow_{*} 0 . On input \\langle 1,3,0,3 \\rangle the successive stack configurations are \\begin{align} & \\underline{1,3,0,3} \\rightarrow_{r10} 3,2,0,\\underline{1,3,0,0} \\rightarrow_{r9} \\underline{3,2,0,1} \\rightarrow_{r11} 1,2,0,\\underline{2,2,0,1} \\rightarrow_{r11} 1,2,0,1,2,0,\\underline{1,2,0,1} \\\\ & \\rightarrow_{r10} 1,2,0,1,2,0,1,1,0,\\underline{1,2,0,0} \\rightarrow_{r8} 1,2,0,1,2,0,\\underline{1,1,0,0} \\rightarrow_{r7} 1,2,0,\\underline{1,2,0,0} \\rightarrow_{r8} \\underline{1,2,0,0} \\rightarrow_{r8} 0. \\end{align} The corresponding equalities are \\begin{align} & H_3(0,3) & = H_2(0,H_2(0,H_1(0,H_2(0,0)))) \\begin{array}{lllllllll} \\text{(r12)} & (x+2) &, n &, a &, b & \\rightarrow & (x+1) &, n &, a &, 1 &, n &, a &, b \\end{array} The successive stack configurations will then be \\begin{align} & \\underline{1,3,0,3} \\rightarrow_{r10} 3,2,0,\\underline{1,3,0,0} \\rightarrow_{r9} \\underline{3,2,0,1} \\rightarrow_{r12} 2,2,0,\\underline{1,2,0,1} \\rightarrow_{r10} 2,2,0,1,1,0,\\underline{1,2,0,0} \\\\ & \\rightarrow_{r8} 2,2,0,\\underline{1,1,0,0} \\rightarrow_{r7} \\underline{2,2,0,0} \\rightarrow_{r12} 1,2,0,\\underline{1,2,0,0} \\rightarrow_{r8} \\underline{1,2,0,0} \\rightarrow_{r8} 0 \\end{align} The corresponding equalities are \\begin{align} & H_3(0,3) & = H^2_2(0,H_1(0,0)) H_3(0,3) = 0 is a special case, see above. The computation of H_{n}(a,b) according to the rules {r6 - r10, r11} is heavily recursive. The culprit is the order in which iteration is executed: H^{n}(a,b) = H(a, H^{n-1}(a,b)) . The first H disappears only after the whole sequence is unfolded. For instance, H_4(2,4) converges to 65536 in 2863311767 steps, the maximum depth of recursion is 65534. The computation according to the rules {r6 - r10, r12} is more efficient in that respect. The implementation of iteration H^{n}(a,b) as H^{n-1}(a, H(a,b)) mimics the repeated execution of a procedure H. The depth of recursion, (n+1), matches the loop nesting. formalized this correspondence. The computation of H_4(2,4) according to the rules {r6-r10, r12} also needs 2863311767 steps to converge on 65536, but the maximum depth of recursion is only 5, as tetration is the 5th operator in the hyperoperation sequence. The considerations above concern the recursion depth only. Either way of iterating leads to the same number of reduction steps, involving the same rules (when the rules r11 and r12 are considered \"the same\"). As the example shows the reduction of H_3(0,3) converges in 9 steps: 1 X r7, 3 X r8, 1 X r9, 2 X r10, 2 X r11/r12. The modus iterandi only affects the order in which the reduction rules are applied. ==See also== Large numbers Fast-growing hierarchy Veblen function",
  "categories": [
    "1516582",
    "23603337",
    "26220375",
    "29176437",
    "29265142",
    "52022518",
    "7692542"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1375889129",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1789920719.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001375889129",
    "type": "webpage",
    "title": "Hyperoperation",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/hyperoperation",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001375889129",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1375889129",
    "note": "Immutable snapshot enwiki-001375889129"
  }
}