Английская Википедия:Hyperoperation

In mathematics, the hyperoperation sequenceШаблон:Refn is an infinite sequence of arithmetic operations (called hyperoperations in this context)Шаблон:Sfn Шаблон:Sfn Шаблон:Sfn that starts with a unary operation (the successor function with n = 0). The sequence continues with the binary operations of addition (n = 1), multiplication (n = 2), and exponentiation (n = 3).

After that, the sequence proceeds with further binary operations extending beyond exponentiation, using right-associativity. For the operations beyond exponentiation, the nth member of this sequence is named by Reuben Goodstein after the Greek prefix of n suffixed with -ation (such as tetration (n = 4), pentation (n = 5), hexation (n = 6), etc.) Шаблон:Sfn and can be written as using n − 2 arrows in Knuth's up-arrow notation. Each hyperoperation may be understood recursively in terms of the previous one by:

<math>a[n]b = \underbrace{a[n-1](a[n-1](a[n-1](\cdots[n-1](a[n-1](a[n-1]a))\cdots)))}_{\displaystyle b \mbox{ copies of } a},\quad n \ge 2</math>

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:

<math>a[n]b = a[n-1]\left(a[n]\left(b - 1\right)\right),\quad n \ge 1</math>

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. <math>50[50]50</math> 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).Шаблон:Sfn

This recursion rule is common to many variants of hyperoperations.

Definition

Definition, most common

The hyperoperation sequence <math>H_n(a,b) \colon (\mathbb{N}_0)^3 \rightarrow \mathbb{N}_0</math> is the sequence of binary operations <math>H_n \colon (\mathbb{N}_0)^2 \rightarrow \mathbb{N}_0</math>, defined recursively as follows:

<math>

 H_n(a,b) = a[n]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}

</math>

(Note that for n = 0, the binary operation essentially reduces to a unary operation (successor function) by ignoring the first argument.)

For n = 0, 1, 2, 3, this definition reproduces the basic arithmetic operations of successor (which is a unary operation), addition, multiplication, and exponentiation, respectively, as

<math>\begin{align}

 H_0(a, b) &= 1 + b, \\
 H_1(a, b) &= a + b, \\
 H_2(a, b) &= a \times b, \\
 H_3(a, b) &= a\uparrow{b} = a^{b}.

\end{align}</math>

The <math>H_n</math> operations for n ≥ 3 can be written in Knuth's up-arrow notation.

So what will be the next operation after exponentiation? We defined multiplication so that <math> H_2(a, 3) = a[2]3 = a \times 3 = a + a + a,</math> and defined exponentiation so that <math> H_3(a, 3) = a[3]3 = a\uparrow 3 = a^3 = a \times a \times a,</math> so it seems logical to define the next operation, tetration, so that <math> H_4(a, 3) = a[4]3 = a\uparrow\uparrow 3 = \operatorname{tetration}(a, 3) = a^{a^a}, </math> with a tower of three 'a'. Analogously, the pentation of (a, 3) will be tetration(a, tetration(a, a)), with three "a" in it.

<math>\begin{align}

 H_4(a,b) &= a\uparrow\uparrow{b}, \\
 H_5(a,b) &= a\uparrow\uparrow\uparrow{b}, \\
   \ldots & \\
 H_n(a,b) &= a\uparrow^{n-2}b \text{ for } n \ge 3, \\
   \ldots & \\

\end{align}</math>

Knuth's notation could be extended to negative indices ≥ −2 in such a way as to agree with the entire hyperoperation sequence, except for the lag in the indexing:

<math>H_n(a, b) = a \uparrow^{n-2}b\text{ for } n \ge 0.</math>

The hyperoperations can thus be seen as an answer to the question "what's next" in the sequence: successor, addition, multiplication, exponentiation, and so on. Noting that

<math>\begin{align}

                a + b &= 1 + (a + (b - 1)) \\
            a \cdot b &= a + (a \cdot (b - 1)) \\
                  a^b &= a \cdot \left(a^{(b - 1)}\right) \\
              a [4] b &= a^{a [4] (b - 1)}

\end{align}</math>

the relationship between basic arithmetic operations is illustrated, allowing the higher operations to be defined naturally as above. The parameters of the hyperoperation hierarchy are sometimes referred to by their analogous exponentiation term; Шаблон:Sfn so a is the base, b is the exponent (or hyperexponent),Шаблон:Sfn and n is the rank (or grade),Шаблон:Sfn and moreover, <math>H_n(a, b)</math> is read as "the bth n-ation of a", e.g. <math>H_4(7,9)</math> is read as "the 9th tetration of 7", and <math>H_{123}(456,789)</math> is read as "the 789th 123-ation of 456".

In common terms, the hyperoperations are ways of compounding numbers that increase in growth based on the iteration of the previous hyperoperation. The concepts of successor, addition, multiplication and exponentiation are all hyperoperations; the successor operation (producing x + 1 from x) is the most primitive, the addition operator specifies the number of times 1 is to be added to itself to produce a final value, multiplication specifies the number of times a number is to be added to itself, and exponentiation refers to the number of times a number is to be multiplied by itself.

Definition, using iteration

Define iteration of a function Шаблон:Math of two variables as

<math>

 f^{x}(a,b) = 
   \begin{cases}
    f(a,b)             & \text{if } x = 1 \\
    f(a, f^{x-1}(a,b)) & \text{if } x > 1
   \end{cases}

</math> The hyperoperation sequence can be defined in terms of iteration, as follows. For all integers <math>x,n,a,b \geq 0,</math> define

<math>

\begin{array}{lcl} H_{0}(a,b) & = & b+1 \\ H_{1}(a,0) & = & a \\ H_{2}(a,0) & = & 0 \\ H_{n+3}(a,0) & = & 1 \\ H_{n+1}(a,b+1) & = & H^{b+1}_{n}(a,H_{n+1}(a,0)) \\ H^{x+2}_{n}(a,b) & = & H_{n}(a,H^{x+1}_{n}(a,b)) \end{array} </math>

As iteration is associative, the last line can be replaced by

<math>

\begin{array}{lcl} H^{x+2}_{n}(a,b) & = & H^{x+1}_{n}(a,H_{n}(a,b)) \end{array} </math>

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

<math>

\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} </math>

To compute <math>H_{n}(a, b)</math> one can use a stack, which initially contains the elements <math>\langle n,a,b \rangle</math>.

Then, repeatedly until no longer possible, three elements are popped and replaced according to the rules^{[nb 1]}

<math>

\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} </math>

Schematically, starting from <math>\langle n,a,b \rangle</math>:

WHILE stackLength <> 1
{
   POP 3 elements;
   PUSH 1 or 5 elements according to the rules r1, r2, r3, r4, r5;
}

Example

Compute <math>H_2(2,2) \rightarrow_{*} 4</math>.Шаблон:Sfn

The reduction sequence is^{[nb 1]}^[1]

<math>\underline{H(S(S(0)),S(S(0)),S(S(0)))}</math>

Шаблон:Space<math>\rightarrow_{r5} H(S(0),S(S(0)),\underline{H(S(S(0)),S(S(0)),S(0))})</math>

Шаблон:Space<math>\rightarrow_{r5} H(S(0),S(S(0)),H(S(0),S(S(0)),\underline{H(S(S(0)),S(S(0)),0)}))</math>

Шаблон:Space<math>\rightarrow_{r3} H(S(0),S(S(0)),\underline{H(S(0),S(S(0)),0)})</math>

Шаблон:Space<math>\rightarrow_{r2} \underline{H(S(0),S(S(0)),S(S(0)))}</math>

Шаблон:Space<math>\rightarrow_{r5} H(0,S(S(0)),\underline{H(S(0),S(S(0)),S(0))})</math>

Шаблон:Space<math>\rightarrow_{r5} H(0,S(S(0)),H(0,S(S(0)),\underline{H(S(0),S(S(0)),0)}))</math>

Шаблон:Space<math>\rightarrow_{r2} H(0,S(S(0)),\underline{H(0,S(S(0)),S(S(0)))})</math>

Шаблон:Space<math>\rightarrow_{r1} \underline{H(0,S(S(0)),S(S(S(0))))}</math>

Шаблон:Space<math>\rightarrow_{r1} S(S(S(S(0))))</math>

When implemented using a stack, on input <math>\langle 2,2,2 \rangle</math>

the stack configurationsШаблон:Space	represent the equations
<math>\underline{2,2,2}</math>	<math>H_2(2,2)</math>
Шаблон:Space<math>\rightarrow_{r5} 1,2,\underline{2,2,1}</math>	Шаблон:Space<math>= H_1(2,H_2(2,1))</math>
Шаблон:Space<math>\rightarrow_{r5} 1,2,1,2,\underline{2,2,0}</math>	Шаблон:Space<math>= H_1(2,H_1(2,H_2(2,0)))</math>
Шаблон:Space<math>\rightarrow_{r3} 1,2,\underline{1,2,0}</math>	Шаблон:Space<math>= H_1(2,H_1(2,0))</math>
Шаблон:Space<math>\rightarrow_{r2} \underline{1,2,2}</math>	Шаблон:Space<math>= H_1(2,2)</math>
Шаблон:Space<math>\rightarrow_{r5} 0,2,\underline{1,2,1}</math>	Шаблон:Space<math>= H_0(2,H_1(2,1))</math>
Шаблон:Space<math>\rightarrow_{r5} 0,2,0,2,\underline{1,2,0}</math>	Шаблон:Space<math>= H_0(2,H_0(2,H_1(2,0)))</math>
Шаблон:Space<math>\rightarrow_{r2} 0,2,\underline{0,2,2}</math>	Шаблон:Space<math>= H_0(2,H_0(2,2))</math>
Шаблон:Space<math>\rightarrow_{r1} \underline{0,2,3}</math>	Шаблон:Space<math>= H_0(2,3)</math>
Шаблон:Space<math>\rightarrow_{r1} 4</math>	Шаблон:Space<math>= 4</math>

TRS based on definition sub 1.2

The definition using iteration leads to a different set of reduction rules

<math>

\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} </math>

As iteration is associative, instead of rule r11 one can define

<math>

\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} </math>

Like in the previous section the computation of <math>H_n(a,b) = H^1_n(a,b)</math> can be implemented using a stack.

Initially the stack contains the four elements <math>\langle 1,n,a,b \rangle</math>.

Then, until termination, four elements are popped and replaced according to the rules^{[nb 1]}

<math>

\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} </math>

Schematically, starting from <math>\langle 1,n,a,b \rangle</math>:

WHILE stackLength <> 1
{
   POP 4 elements;
   PUSH 1 or 7 elements according to the rules r6, r7, r8, r9, r10, r11;
}

Example

Compute <math>H_3(0,3) \rightarrow_{*} 0</math>.

On input <math>\langle 1,3,0,3 \rangle</math> the successive stack configurations are

<math>\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}</math>

The corresponding equalities are

<math>\begin{align}

& H_3(0,3)

 = H^3_2(0,H_3(0,0))
 = H^3_2(0,1)
 = H_2(0,H^2_2(0,1))
 = H_2(0,H_2(0,H_2(0,1)) \\

& = H_2(0,H_2(0,H_1(0,H_2(0,0))))

 = H_2(0,H_2(0,H_1(0,0)))
 = H_2(0,H_2(0,0))
 = H_2(0,0)
 = 0.

\end{align}</math>

When reduction rule r11 is replaced by rule r12, the stack is transformed acoording to

<math>\begin{array}{lllllllll}

\text{(r12)} & (x+2) &, n &, a &, b & \rightarrow & (x+1) &, n &, a &, 1 &, n &, a &, b \end{array}</math>

The successive stack configurations will then be

<math>\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}</math>

The corresponding equalities are

<math>\begin{align}

& H_3(0,3)

 = H^3_2(0,H_3(0,0))
 = H^3_2(0,1)
 = H^2_2(0,H_2(0,1))
 = H^2_2(0,H_1(0,H_2(0,0))) \\

& = H^2_2(0,H_1(0,0))

 = H^2_2(0,0)
 = H_2(0,H_2(0,0))
 = H_2(0,0)
 = 0

\end{align}</math>

Remarks

<math>H_3(0,3) = 0</math> is a special case. See below.^{[nb 2]}^{[nb 3]}
The computation of <math>H_{n}(a,b)</math> according to the rules {r6 - r10, r11} is heavily recursive. The culprit is the order in which iteration is executed: <math>H^{n}(a,b) = H(a, H^{n-1}(a,b))</math>. The first <math>H</math> disappears only after the whole sequence is unfolded. For instance, <math>H_4(2,4)</math> converges to 65536 in 2863311767 steps, the maximum depth of recursion^[2] is 65534.
The computation according to the rules {r6 - r10, r12} is more efficient in that respect. The implementation of iteration <math>H^{n}(a,b)</math> as <math>H^{n-1}(a, H(a,b))</math> mimics the repeated execution of a procedure H.^[3] The depth of recursion, (n+1), matches the loop nesting. Шаблон:Harvtxt formalized this correspondence. The computation of <math>H_4(2,4)</math> 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 <math>H_3(0,3)</math> 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.

Examples

Below is a list of the first seven (0th to 6th) hyperoperations (0⁰ is defined as 1).

n	Operation, H_n(a, b)	Definition	Names	Domain
0	<math>1 + b</math> or <math>a [0] b</math>	<math>1 + \underbrace{1 + 1 + 1 + \cdots + 1 + 1 + 1}_{\displaystyle b \mbox{ copies of 1}}</math>	hyper0, increment, successor, zeration	Arbitrary
1	<math>a + b</math> or <math>a [1] b</math>	<math>a + \underbrace{1 + 1 + 1 + \cdots + 1 + 1 + 1}_{\displaystyle b \mbox{ copies of 1}}</math>	hyper1, addition
2	<math>a \cdot b</math> or <math>a [2] b</math>	<math>\underbrace{a + a + a + \cdots + a + a + a}_{\displaystyle b \mbox{ copies of } a}</math>	hyper2, multiplication
3	<math>a^b</math> or <math>a [3] b</math>	<math>\underbrace{a \cdot a \cdot a \cdot \;\cdots\; \cdot a \cdot a \cdot a}_{\displaystyle b \mbox{ copies of } a}</math>	hyper3, exponentiation	b real, with some multivalued extensions to complex numbers
4	<math>^{b}a</math> or <math>a [4] b</math>	<math>\underbrace{a[3](a[3](a[3](\cdots[3](a[3](a[3]a))\cdots)))}_{\displaystyle b \mbox{ copies of } a}</math>	hyper4, tetration	a ≥ 0 or an integer, b an integer ≥ −1 ^{[nb 4]} (with some proposed extensions)
5	<math>a [5] b</math>	<math>\underbrace{a[4](a[4](a[4](\cdots[4](a[4](a[4]a))\cdots)))}_{\displaystyle b \mbox{ copies of } a}</math>	hyper5, pentation	a, b integers ≥ −1 ^{[nb 4]}
6	<math>a [6] b</math>	<math>\underbrace{a[5](a[5](a[5](\cdots[5](a[5](a[5]a))\cdots)))}_{\displaystyle b \mbox{ copies of } a}</math>	hyper6, hexation	a, b integers ≥ −1 ^{[nb 4]}

Special cases

H_n(0, b) =

b + 1, when n = 0

b, when n = 1

0, when n = 2

1, when n = 3 and b = 0 ^{[nb 2]}^{[nb 3]}

0, when n = 3 and b > 0 ^{[nb 2]}^{[nb 3]}

1, when n > 3 and b is even (including 0)

0, when n > 3 and b is odd

H_n(1, b) =

b, when n = 2

1, when n ≥ 3

H_n(a, 0) =

0, when n = 2

1, when n = 0, or n ≥ 3

a, when n = 1

H_n(a, 1) =

a, when n ≥ 2

H_n(a, a) =

H_n+1(a, 2), when n ≥ 1

H_n(a, −1) =^{[nb 4]}

0, when n = 0, or n ≥ 4

a − 1, when n = 1

−a, when n = 2

Шаблон:Sfrac , when n = 3

H_n(2, 2) =

3, when n = 0

4, when n ≥ 1, easily demonstrable recursively.

History

One of the earliest discussions of hyperoperations was that of Albert Bennett Шаблон:Sfn in 1914, who developed some of the theory of commutative hyperoperations (see below). About 12 years later, Wilhelm Ackermann defined the function <math>\phi(a, b, n)</math> Шаблон:Sfn which somewhat resembles the hyperoperation sequence.

In his 1947 paper,Шаблон:Sfn 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., <math>G(n, a, b) = H_n(a, b)</math>, the hyperoperation sequence as a whole is seen to be a version of the original Ackermann function <math>\phi(a, b, n)</math> — 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 <math>\phi</math> 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, <math>\phi(a, b, n)</math> defines a sequence of operations starting from addition (n = 0) rather than the successor function, then multiplication (n = 1), exponentiation (n = 2), etc. Secondly, the initial conditions for <math>\phi</math> result in <math>\phi(a, b, 3) = G(4,a,b+1) = a [4] (b + 1)</math>, thus differing from the hyperoperations beyond exponentiation.Шаблон:Sfn Шаблон:Sfn Шаблон:Sfn The significance of the b + 1 in the previous expression is that <math>\phi(a, b, 3)</math> = <math>a^{a^{\cdot^{\cdot^{\cdot^a}}}}</math>, where b counts the number of operators (exponentiations), rather than counting the number of operands ("a"s) as does the b in <math>a [4] b</math>, and so on for the higher-level operations. (See the Ackermann function article for details.)

Notations

This is a list of notations that have been used for hyperoperations.

Name	Notation equivalent to <math>H_n(a, b)</math>	Comment
Knuth's up-arrow notation	<math>a \uparrow^{n-2} b</math>	Used by Knuth Шаблон:Sfn (for n ≥ 3), and found in several reference books.Шаблон:Sfn Шаблон:Sfn
Hilbert's notation	<math>\phi_n(a, b)</math>	Used by David Hilbert.Шаблон:Sfn
Goodstein's notation	<math>G(n, a, b)</math>	Used by Reuben Goodstein.Шаблон:Sfn
Original Ackermann function	<math> \begin{matrix} \phi(a, b, n-1) \ \text{ for } 1 \le n \le 3 \\ \phi(a, b-1, n-1) \ \text{ for } n \ge 4 \end{matrix} </math>	Used by Wilhelm Ackermann (for n ≥ 1)Шаблон:Sfn
Ackermann–Péter function	<math>A(n, b - 3) + 3 \ \text{for } a = 2</math>	This corresponds to hyperoperations for base 2 (a = 2)
Nambiar's notation	<math>a \otimes^{n-1} b</math>	Used by Nambiar (for n ≥ 1) Шаблон:Sfn
Superscript notation	<math>a {}^{(n)} b</math>	Used by Robert Munafo.Шаблон:Sfn
Subscript notation (for lower hyperoperations)	<math>a {}_{(n)} b</math>	Used for lower hyperoperations by Robert Munafo.Шаблон:Sfn
Operator notation (for "extended operations")	<math>a O_{n-1} b</math>	Used for lower hyperoperations by John Doner and Alfred Tarski (for n ≥ 1).Шаблон:Sfn
Square bracket notation	<math>a[n]b</math>	Used in many online forums; convenient for ASCII.
Conway chained arrow notation	<math>a \to b \to (n-2) </math>	Used by John Horton Conway (for n ≥ 3)

Variant starting from a

Шаблон:Main

In 1928, Wilhelm Ackermann defined a 3-argument function <math>\phi(a, b, n)</math> which gradually evolved into a 2-argument function known as the Ackermann function. The original Ackermann function <math>\phi</math> was less similar to modern hyperoperations, because his initial conditions start with <math>\phi(a, 0, n) = a</math> for all n > 2. Also he assigned addition to n = 0, multiplication to n = 1 and exponentiation to n = 2, so the initial conditions produce very different operations for tetration and beyond.

n	Operation	Comment
0	<math>F_0(a, b) = a + b</math>
1	<math>F_1(a, b) = a \cdot b</math>
2	<math>F_2(a, b) = a^b</math>
3	<math>F_3(a, b) = a [4] (b + 1)</math>	An offset form of tetration. The iteration of this operation is different than the iteration of tetration.
4	<math>F_4(a, b) = (x \mapsto a [4] (x + 1))^b(a)</math>	Not to be confused with pentation.

Another initial condition that has been used is <math>A(0, b) = 2b + 1</math> (where the base is constant <math>a = 2</math>), due to Rózsa Péter, which does not form a hyperoperation hierarchy.

Variant starting from 0

In 1984, C. W. Clenshaw and F. W. J. Olver began the discussion of using hyperoperations to prevent computer floating-point overflows.Шаблон:Sfn Since then, many other authors Шаблон:Sfn Шаблон:Sfn Шаблон:Sfn have renewed interest in the application of hyperoperations to floating-point representation. (Since H_n(a, b) are all defined for b = -1.) While discussing tetration, Clenshaw et al. assumed the initial condition <math>F_n(a, 0) = 0</math>, which makes yet another hyperoperation hierarchy. Just like in the previous variant, the fourth operation is very similar to tetration, but offset by one.

n	Operation	Comment
0	<math>F_0(a, b) = b + 1</math>
1	<math>F_1(a, b) = a + b</math>
2	<math>F_2(a, b) = a\cdot b = e^{\ln(a) + \ln(b)}</math>
3	<math>F_3(a, b) = a^b</math>
4	<math>F_4(a, b) = a [4] (b - 1)</math>	An offset form of tetration. The iteration of this operation is much different than the iteration of tetration.
5	<math>F_5(a, b) = \left(x \mapsto a [4] (x - 1)\right)^b(0) = 0 \text{ if } a>0</math>	Not to be confused with pentation.

Lower hyperoperations

An alternative for these hyperoperations is obtained by evaluation from left to right.Шаблон:Sfn Since

<math>\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}</math> define (with ° or subscript)

<math>a_{(n+1)}b = \left(a_{(n + 1)}(b - 1)\right)_{(n)} a</math>

with

<math>\begin{align}

 a_{(1)} b &= a + b \\
 a_{(2)} 0 &= 0 \\
 a_{(n)} 1 &= a & \text{for } n>2 \\

\end{align}</math>

This was extended to ordinal numbers by Doner and Tarski,Шаблон:Sfn by :

<math>\begin{align}

      \alpha O_0 \beta &= \alpha + \beta \\
 \alpha O_\gamma \beta &= \sup\limits_{\eta<\beta, \xi<\gamma}(\alpha O_\gamma \eta) O_\xi \alpha

\end{align}</math>

It follows from Definition 1(i), Corollary 2(ii), and Theorem 9, that, for a ≥ 2 and b ≥ 1, that Шаблон:Original research inline

But this suffers a kind of collapse, failing to form the "power tower" traditionally expected of hyperoperators:Шаблон:Sfn^{[nb 5]}

<math>\alpha_{(4)}(1 + \beta) = \alpha^{\left(\alpha^\beta\right)}.</math>

If α ≥ 2 and γ ≥ 2,Шаблон:Sfn^{[Corollary 33(i)]}^{[nb 5]}

<math>\alpha_{(1 + 2\gamma + 1)}\beta \leq \alpha_{(1 + 2\gamma)}(1 + 3\alpha\beta).</math>

n	Operation	Comment
0	<math>F_0(a, b) = a + 1</math>	increment, successor, zeration
1	<math>F_1(a, b) = a + b</math>
2	<math>F_2(a, b) = a\cdot b</math>
3	<math>F_3(a, b) = a^b</math>
4	<math>F_4(a, b) = a^{\left(a^{(b-1)}\right)}</math>	Not to be confused with tetration.
5	<math>F_5(a, b) = \left(x \mapsto x^{x^{(a-1)}}\right)^{b-1}(a)</math>	Not to be confused with pentation. Similar to tetration.

Commutative hyperoperations

Commutative hyperoperations were considered by Albert Bennett as early as 1914,Шаблон:Sfn which is possibly the earliest remark about any hyperoperation sequence. Commutative hyperoperations are defined by the recursion rule

which is symmetric in a and b, meaning all hyperoperations are commutative. This sequence does not contain exponentiation, and so does not form a hyperoperation hierarchy.

n	Operation	Comment
0	<math>F_0(a, b) = \ln\left(e^a + e^b\right)</math>	Smooth maximum
1	<math>F_1(a, b) = a + b</math>
2	<math>F_2(a, b) = a\cdot b = e^{\ln(a) + \ln(b)}</math>	This is due to the properties of the logarithm.
3	<math>F_3(a, b) = a^{\ln(b)} = e^{\ln(a)\ln(b)}</math>
4	<math>F_4(a, b) = e^{e^{\ln(\ln(a))\ln(\ln(b))}}</math>	Not to be confused with tetration.

Numeration systems based on the hyperoperation sequence

R. L. Goodstein Шаблон:Sfn used the sequence of hyperoperators to create systems of numeration for the nonnegative integers. The so-called complete hereditary representation of integer n, at level k and base b, can be expressed as follows using only the first k hyperoperators and using as digits only 0, 1, ..., b − 1, together with the base b itself:

For 0 ≤ n ≤ b − 1, n is represented simply by the corresponding digit.
For n > b − 1, the representation of n is found recursively, first representing n in the form

b [k] x_k [k − 1] x_{k − 1} [k - 2] ... [2] x₂ [1] x₁

where x_k, ..., x₁ are the largest integers satisfying (in turn)

b [k] x_k ≤ n

b [k] x_k [k − 1] x_{k − 1} ≤ n

...

b [k] x_k [k − 1] x_{k − 1} [k - 2] ... [2] x₂ [1] x₁ ≤ n

Any x_i exceeding b − 1 is then re-expressed in the same manner, and so on, repeating this procedure until the resulting form contains only the digits 0, 1, ..., b − 1, together with the base b.

Unnecessary parentheses can be avoided by giving higher-level operators higher precedence in the order of evaluation; thus,

level-1 representations have the form b [1] X, with X also of this form;

level-2 representations have the form b [2] X [1] Y, with X,Y also of this form;

level-3 representations have the form b [3] X [2] Y [1] Z, with X,Y,Z also of this form;

level-4 representations have the form b [4] X [3] Y [2] Z [1] W, with X,Y,Z,W also of this form;

and so on.

In this type of base-b hereditary representation, the base itself appears in the expressions, as well as "digits" from the set {0, 1, ..., b − 1}. This compares to ordinary base-2 representation when the latter is written out in terms of the base b; e.g., in ordinary base-2 notation, 6 = (110)₂ = 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

Notes

Шаблон:Reflist

References

Шаблон:Reflist

Bibliography

Шаблон:Refbegin

Шаблон:Cite journal

Шаблон:Cite journal

Шаблон:Cite book

Шаблон:Cite web

Шаблон:Cite journal

Шаблон:Cite journal

Шаблон:Cite journal

Шаблон:Cite web

Шаблон:Cite journal

Шаблон:Cite journal

Шаблон:Cite web

Шаблон:Cite web

Шаблон:Cite journal

Шаблон:Cite journal

Шаблон:Cite journal

Шаблон:Cite journal

Шаблон:Cite journal

Шаблон:Cite conference

Шаблон:Cite web

Шаблон:Cite web

Шаблон:Cite web

Шаблон:Cite journal

Шаблон:Cite journal

Шаблон:Cite book

Шаблон:Cite web

Шаблон:Cite web

Шаблон:Cite web

Шаблон:Cite web

Шаблон:Cite book

Шаблон:Cite web

Шаблон:Cite web

Шаблон:Cite book

Шаблон:Refend

Шаблон:Hyperoperations Шаблон:Large numbers

Ошибка цитирования Для существующих тегов <ref> группы «nb» не найдено соответствующего тега <references group="nb"/>

↑ In each step the underlined redex is rewritten.
↑ The maximum depth of recursion refers to the number of levels of activation of a procedure which exist during the deepest call of the procedure. Шаблон:Harvtxt
↑ LOOP n TIMES DO H.

[2] In each step the underlined redex is rewritten.

[5] The maximum depth of recursion refers to the number of levels of activation of a procedure which exist during the deepest call of the procedure. Шаблон:Harvtxt

[6] LOOP n TIMES DO H.

[nb 1]

[1]

[nb 2]

[nb 3]

[2]

[3]

[nb 4]

[nb 5]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.

Английская Википедия:Hyperoperation

Содержание

Definition

Definition, most common

Definition, using iteration

Computation

TRS based on definition sub 1.1

TRS based on definition sub 1.2

Examples

Special cases

History

Notations

Variant starting from a

Variant starting from 0

Lower hyperoperations

Commutative hyperoperations

Numeration systems based on the hyperoperation sequence

See also

Notes

References

Bibliography

Навигация

Действия на странице

Действия на странице

Персональные инструменты

Навигация

Поиск

Инструменты