Movatterモバイル変換


[0]ホーム

URL:


Jump to content
WikipediaThe Free Encyclopedia
Search

Hyperoperation

From Wikipedia, the free encyclopedia
Generalization of addition, multiplication, exponentiation, tetration, etc.
This article is about the arithmetic concept. For the group theory hyperoperation concept, seeHyperstructure.

Inmathematics, thehyperoperation sequence is an infinitesequence of arithmetic operations (calledhyperoperations in this context)[1][2][3] that starts with aunary operation (thesuccessor function withn = 0). The sequence continues with thebinary operations ofaddition (n = 1),multiplication (n = 2), andexponentiation (n = 3).[nb 1] After that, the sequence proceeds with further binary operations extending beyond exponentiation, usingright-associativity. For the operations beyond exponentiation, thenth member of this sequence is named byReuben Goodstein after theGreek prefix ofn suffixed with-ation (such astetration (n = 4), pentation (n = 5), hexation (n = 6), etc.)[7] and can be written usingn − 2 arrows inKnuth's up-arrow notation.Each hyperoperation may be understoodrecursively in terms of the previous one by:

a[n]b=a[n1](a[n1](a[n1](a[n1](a[n1](a[n1]a)))))b copies of a,n2{\displaystyle 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\geq 2}

It may also be defined according to the recursion rule part of the definition, as in Knuth's up-arrow version of theAckermann function:

a[n]b=a[n1](a[n](b1)),n1{\displaystyle a[n]b=a[n-1]\left(a[n]\left(b-1\right)\right),\quad n\geq 1}

This can be used to easily show numbers much larger than those whichscientific notation can, such asSkewes's number andgoogolplexplex (e.g.50[50]50{\displaystyle 50[50]50} is much larger than Skewes's number and googolplexplex), but there are some numbers which even they cannot easily show, such asGraham's number andTREE(3).[14]

This recursion rule is common to many variants of hyperoperations.

Definition

[edit]

Thehyperoperation sequence is thesequence ofbinary operationsHn:(N0)2N0{\displaystyle H_{n}\colon (\mathbb {N} _{0})^{2}\rightarrow \mathbb {N} _{0}} definedrecursively as follows:Hn(a,b)={b+1if n=0aif n=1 and b=00if n=2 and b=01if n3 and b=0Hn1(a,Hn(a,b1))otherwise.{\displaystyle 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\geq 3{\text{ and }}b=0\\H_{n-1}(a,H_{n}(a,b-1))&{\text{otherwise}}\end{cases}}.}Forn = 0, 1, 2, 3, this definition reproduces the basic arithmetic operations ofsuccessor (which is a unary operation),addition,multiplication, andexponentiation, respectively, asH0(a,b)=b+1,H1(a,b)=a+b,H2(a,b)=a×b,H3(a,b)=ab{\displaystyle {\begin{aligned}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{aligned}}}for all nonnegative integersa andb. The hyperoperations can thus be seen as an answer to the question "what's next?" in thesequence 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,H4(a,3)=tetration(a,3)=aaa{\displaystyle H_{4}(a,3)=\operatorname {tetration} (a,3)=a^{a^{a}}} is a power tower of threeas, andH4(a,4)=tetration(a,4)=aaaa{\displaystyle H_{4}(a,4)=\operatorname {tetration} (a,4)=a^{a^{a^{a}}}}. Likewise the fifth hyperoperationpentation, is defined by iterated tetration, so thatH5(a,3)=tetration(a,tetration(a,a)){\displaystyle 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;[15] soa is thebase,b is theexponent (orhyperexponent),[13] andn is therank (orgrade).[8] In general,Hn(a,b){\displaystyle H_{n}(a,b)} may be read as "thebthn-ation ofa", so thatH4(7,9){\displaystyle H_{4}(7,9)} is read as "the 9th tetration of 7", andH123(456,789){\displaystyle H_{123}(456,789)} is read as "the 789th 123-ation of 456".

An alternative way of writing hyperoperations is the compact notationa[n]b{\displaystyle a[n]b} forHn(a,b){\displaystyle H_{n}(a,b)}. In this notation, exponentiation is denoteda[3]b=ab{\displaystyle a[3]b=a^{b}}, tetration is denoteda[4]b{\displaystyle a[4]b} (so thata[4]3=aaa{\displaystyle a[4]3=a^{a^{a}}}, pentation is denoteda[5]b{\displaystyle a[5]b}, and so on. Hyperoperations can also be expressed usingKnuth's up-arrow notation. In this notation,ab{\displaystyle a\uparrow b} represents the exponentiation functionab{\displaystyle a^{b}},a↑↑b{\displaystyle a\uparrow \uparrow b} represents tetration,a↑↑↑b{\displaystyle a\uparrow \uparrow \uparrow b} ora3b{\displaystyle a\uparrow ^{3}b} represents the pentationa[5]b{\displaystyle a[5]b}, and more generallyHn(a,b)=an2b{\displaystyle H_{n}(a,b)=a\uparrow ^{n-2}b} forn0.{\displaystyle n\geq 0.} Yet another alternative isConway chained arrow notation. In this notation, one hasHn(a,b)=a[n]b=abn2{\displaystyle H_{n}(a,b)=a[n]b=a\rightarrow b\rightarrow n-2}, so that (for example)a[5]b=ab3{\displaystyle a[5]b=a\rightarrow b\rightarrow 3}.[16]

Examples

[edit]

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

nOperation,
Hn(a,b)
DefinitionNamesDomain
0b+1{\displaystyle b+1} ora[0]b{\displaystyle a[0]b}1+1+1++1+1+1b copies of 1+1{\displaystyle \underbrace {1+1+1+\cdots +1+1+1} _{\displaystyle b{\mbox{ copies of 1}}}+1}Increment,successor, zeration, hyper0Arbitrary
1a+b{\displaystyle a+b} ora[1]b{\displaystyle a[1]b}a+1+1+1++1+1+1b copies of 1{\displaystyle a+\underbrace {1+1+1+\cdots +1+1+1} _{\displaystyle b{\mbox{ copies of 1}}}}Addition, hyper1
2a×b{\displaystyle a\times {b}} ora[2]b{\displaystyle a[2]b}a+a+a++a+a+ab copies of a{\displaystyle \underbrace {a+a+a+\cdots +a+a+a} _{\displaystyle b{\mbox{ copies of }}a}}Multiplication, hyper2
3ab{\displaystyle a^{b}} ora[3]b{\displaystyle a[3]b}a×a×a××a×a×ab copies of a{\displaystyle \underbrace {a\times a\times a\times \;\cdots \;\times a\times a\times a} _{\displaystyle b{\mbox{ copies of }}a}}Exponentiation, hyper3b real, with some multivalued extensions tocomplex numbers
4ba{\displaystyle ^{b}a} ora[4]b{\displaystyle a[4]b}a[3](a[3](a[3]([3](a[3](a[3]a)))))b copies of a{\displaystyle \underbrace {a[3](a[3](a[3](\cdots [3](a[3](a[3]a))\cdots )))} _{\displaystyle b{\mbox{ copies of }}a}}Tetration, hyper4a ≥ 0 or an integer,b an integer ≥ −1[nb 2] (with some proposed extensions)
5ba{\displaystyle _{b}a} ora[5]b{\displaystyle a[5]b}a[4](a[4](a[4]([4](a[4](a[4]a)))))b copies of a{\displaystyle \underbrace {a[4](a[4](a[4](\cdots [4](a[4](a[4]a))\cdots )))} _{\displaystyle b{\mbox{ copies of }}a}}Pentation, hyper5a,b integers ≥ −1[nb 2]
6a[6]b{\displaystyle a[6]b}a[5](a[5](a[5]([5](a[5](a[5]a)))))b copies of a{\displaystyle \underbrace {a[5](a[5](a[5](\cdots [5](a[5](a[5]a))\cdots )))} _{\displaystyle b{\mbox{ copies of }}a}}Hexation, hyper6

Special cases

[edit]

Hn(0,b) =

b + 1, whenn = 0
b, whenn = 1
0, whenn = 2
1, whenn = 3 andb = 0[nb 3]
0, whenn = 3 andb > 0[nb 3]
1, whenn > 3 andb is even (including 0)
0, whenn > 3 andb is odd

Hn(1,b) =

b, whenn = 2
1, whenn ≥ 3

Hn(a, 0) =

0, whenn = 2
1, whenn = 0, orn ≥ 3
a, whenn = 1

Hn(a, 1) =

2, whenn = 0
a + 1, whenn = 1
a, whenn ≥ 2

Hn(a,a) =

Hn+1(a, 2), whenn ≥ 1

Hn(a, −1) =[nb 2]

0, whenn = 0, orn ≥ 4
a − 1, whenn = 1
a, whenn = 2
1/a , whenn = 3

Hn(2, 2) =

3, whenn = 0
4, whenn ≥ 1, easily demonstrable recursively.

History

[edit]

One of the earliest discussions of hyperoperations was that of Albert Bennett in 1914, who developed some of the theory ofcommutative hyperoperations (see§ Commutative hyperoperations below).[8] About 12 years later,Wilhelm Ackermann defined the functionϕ(a,b,n){\displaystyle \phi (a,b,n)}, which somewhat resembles the hyperoperation sequence.[17]

In his 1947 paper,[7]Reuben Goodstein introduced the specific sequence of operations that are now calledhyperoperations, and also suggested the Greek namestetration, 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)=Hn(a,b){\displaystyle G(n,a,b)=H_{n}(a,b)}, the hyperoperation sequence as a whole is seen to be a version of the originalAckermann functionϕ(a,b,n){\displaystyle \phi (a,b,n)}recursive but notprimitive recursive — as modified by Goodstein to incorporate the primitivesuccessor 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-argumentAckermann functionϕ{\displaystyle \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,ϕ(a,b,n){\displaystyle \phi (a,b,n)} defines a sequence of operations starting from addition (n = 0) rather than thesuccessor function, then multiplication (n = 1), exponentiation (n = 2), etc. Secondly, the initial conditions forϕ{\displaystyle \phi } result inϕ(a,b,3)=G(4,a,b+1)=a[4](b+1){\displaystyle \phi (a,b,3)=G(4,a,b+1)=a[4](b+1)}, thus differing from the hyperoperations beyond exponentiation.[9][18][19] The significance of theb + 1 in the previous expression is thatϕ(a,b,3){\displaystyle \phi (a,b,3)} =aaa{\displaystyle a^{a^{\cdot ^{\cdot ^{\cdot ^{a}}}}}}, whereb counts the number ofoperators (exponentiations), rather than counting the number ofoperands ("a"s) as does theb ina[4]b{\displaystyle a[4]b}, and so on for the higher-level operations. (See theAckermann function article for details.)

Notations

[edit]

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

NameNotation equivalent toHn(a,b){\displaystyle H_{n}(a,b)}Comment
Knuth's up-arrow notationan2b{\displaystyle a\uparrow ^{n-2}b}Used byKnuth[20] (forn ≥ 3), and found in several reference books.[21][22]
Hilbert's notationϕn(a,b){\displaystyle \phi _{n}(a,b)}Used byDavid Hilbert.[23]
Goodstein's notationG(n,a,b){\displaystyle G(n,a,b)}Used byReuben Goodstein.[7]
OriginalAckermann functionϕ(a,b,n1)  for 1n3ϕ(a,b1,n1)  for n4{\displaystyle {\begin{matrix}\phi (a,b,n-1)\ {\text{ for }}1\leq n\leq 3\\\phi (a,b-1,n-1)\ {\text{ for }}n\geq 4\end{matrix}}}Used byWilhelm Ackermann (forn ≥ 1)[17]
Ackermann–Péter functionA(n,b3)+3 for a=2{\displaystyle A(n,b-3)+3\ {\text{for }}a=2}This corresponds to hyperoperations for base 2 (a = 2)
Nambiar's notationan1b{\displaystyle a\otimes ^{n-1}b}Used by Nambiar (forn ≥ 1)[24]
Superscript notationa(n)b{\displaystyle a{}^{(n)}b}Used byRobert Munafo.[18]
Subscript notation (for lower hyperoperations)a(n)b{\displaystyle a{}_{(n)}b}Used for lower hyperoperations by Robert Munafo.[18]
Operator notation (for "extended operations")aOn1b{\displaystyle aO_{n-1}b}Used for lower hyperoperations byJohn Doner andAlfred Tarski (forn ≥ 1).[25]
Square bracket notationa[n]b{\displaystyle a[n]b}Used in many online forums; convenient forASCII.
Conway chained arrow notationab(n2){\displaystyle a\to b\to (n-2)}Used byJohn Horton Conway (forn ≥ 3)

Variant starting froma

[edit]
Main article:Ackermann function

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

nOperationComment
0F0(a,b)=a+b{\displaystyle F_{0}(a,b)=a+b}
1F1(a,b)=ab{\displaystyle F_{1}(a,b)=a\cdot b}
2F2(a,b)=ab{\displaystyle F_{2}(a,b)=a^{b}}
3F3(a,b)=a[4](b+1){\displaystyle F_{3}(a,b)=a[4](b+1)}An offset form oftetration. The iteration of this operation is different than theiteration of tetration.
4F4(a,b)=(xa[4](x+1))b(a){\displaystyle F_{4}(a,b)=(x\mapsto a[4](x+1))^{b}(a)}Not to be confused with pentation.

Another initial condition that has been used isA(0,b)=2b+1{\displaystyle A(0,b)=2b+1} (where the base is constanta=2{\displaystyle a=2}), due toRózsa Péter, which does not form a hyperoperation hierarchy.

Variant starting from 0

[edit]

In 1984, C. W. Clenshaw and F. W. J. Olver began the discussion of using hyperoperations to prevent computerfloating-point overflows.[26]Since then, many other authors[27][28][29] have renewed interest in the application of hyperoperations tofloating-point representation. (SinceHn(a,b) are all defined forb = -1.) While discussingtetration, Clenshawet al. assumed the initial conditionFn(a,0)=0{\displaystyle F_{n}(a,0)=0}, which makes yet another hyperoperation hierarchy. Just like in the previous variant, the fourth operation is very similar totetration, but offset by one.

nOperationComment
0F0(a,b)=b+1{\displaystyle F_{0}(a,b)=b+1}
1F1(a,b)=a+b{\displaystyle F_{1}(a,b)=a+b}
2F2(a,b)=ab=eln(a)+ln(b){\displaystyle F_{2}(a,b)=a\cdot b=e^{\ln(a)+\ln(b)}}
3F3(a,b)=ab{\displaystyle F_{3}(a,b)=a^{b}}
4F4(a,b)=a[4](b1){\displaystyle F_{4}(a,b)=a[4](b-1)}An offset form oftetration. The iteration of this operation is much different than theiteration of tetration.
5F5(a,b)=(xa[4](x1))b(0)=0 if a>0{\displaystyle F_{5}(a,b)=\left(x\mapsto a[4](x-1)\right)^{b}(0)=0{\text{ if }}a>0}Not to be confused with pentation.

Lower hyperoperations

[edit]

An alternative for these hyperoperations is obtained by evaluation from left to right.[11] Since

a+b=(a+(b1))+1ab=(a(b1))+aab=(a(b1))a{\displaystyle {\begin{aligned}a+b&=(a+(b-1))+1\\a\cdot b&=(a\cdot (b-1))+a\\a^{b}&=\left(a^{(b-1)}\right)\cdot a\end{aligned}}}

define (with ° or subscript)

a(n+1)b=(a(n+1)(b1))(n)a{\displaystyle a_{(n+1)}b=\left(a_{(n+1)}(b-1)\right)_{(n)}a}

with

a(1)b=a+ba(2)0=0a(n)1=afor n>2{\displaystyle {\begin{aligned}a_{(1)}b&=a+b\\a_{(2)}0&=0\\a_{(n)}1&=a&{\text{for }}n>2\\\end{aligned}}}

This was extended to ordinal numbers by Doner and Tarski,[30] by :

αO0β=α+βαOνβ=supδ<β, μ<ν(αOνδ)Oμα{\displaystyle {\begin{aligned}\alpha O_{0}\beta &=\alpha +\beta \\\alpha O_{\nu }\beta &=\sup \limits _{\delta <\beta ,~\mu <\nu }(\alpha O_{\nu }\delta )O_{\mu }\alpha \end{aligned}}}

It follows from Definition 1(i), Corollary 2(ii), and Theorem 9, that, fora ≥ 2 andb ≥ 1, that[original research?]

aOnb=a(n+1)b{\displaystyle aO_{n}b=a_{(n+1)}b}

But this suffers a kind of collapse, failing to form the "power tower" traditionally expected of hyperoperators:[31][nb 4]

α(4)(1+β)=α(αβ).{\displaystyle \alpha _{(4)}(1+\beta )=\alpha ^{\left(\alpha ^{\beta }\right)}.}

If α ≥ 2 and γ ≥ 2,[25][Corollary 33(i)][nb 4]

α(1+2ν+1)βα(1+2ν)(1+3αβ).{\displaystyle \alpha _{(1+2\nu +1)}\beta \leq \alpha _{(1+2\nu )}(1+3\alpha \beta ).}
nOperationComment
0F0(a,b)=a+1{\displaystyle F_{0}(a,b)=a+1}Increment, successor, zeration
1F1(a,b)=a+b{\displaystyle F_{1}(a,b)=a+b}
2F2(a,b)=ab{\displaystyle F_{2}(a,b)=a\cdot b}
3F3(a,b)=ab{\displaystyle F_{3}(a,b)=a^{b}}
4F4(a,b)=a(a(b1)){\displaystyle F_{4}(a,b)=a^{\left(a^{(b-1)}\right)}}Not to be confused withtetration.
5F5(a,b)=(xxx(a1))b1(a){\displaystyle F_{5}(a,b)=\left(x\mapsto x^{x^{(a-1)}}\right)^{b-1}(a)}Not to be confused with pentation.
Similar totetration.

Commutative hyperoperations

[edit]

Commutative hyperoperations were considered by Albert Bennett as early as 1914,[8] which is possibly the earliest remark about any hyperoperation sequence. Commutative hyperoperations are defined by the recursion rule

Fn+1(a,b)=exp(Fn(ln(a),ln(b))){\displaystyle F_{n+1}(a,b)=\exp(F_{n}(\ln(a),\ln(b)))}

which is symmetric ina andb, meaning all hyperoperations are commutative. This sequence does not containexponentiation, and so does not form a hyperoperation hierarchy.

nOperationComment
0F0(a,b)=ln(ea+eb){\displaystyle F_{0}(a,b)=\ln \left(e^{a}+e^{b}\right)}Smooth maximum (LogSumExp)
1F1(a,b)=a+b{\displaystyle F_{1}(a,b)=a+b}
2F2(a,b)=ab=eln(a)+ln(b){\displaystyle F_{2}(a,b)=a\cdot b=e^{\ln(a)+\ln(b)}}This is due to theproperties of the logarithm.
3F3(a,b)=aln(b)=eln(a)ln(b){\displaystyle F_{3}(a,b)=a^{\ln(b)}=e^{\ln(a)\ln(b)}}In afinite field, this is theDiffie–Hellman key exchange operation.
4F4(a,b)=eeln(ln(a))ln(ln(b)){\displaystyle F_{4}(a,b)=e^{e^{\ln(\ln(a))\ln(\ln(b))}}}Not to be confused withtetration.

Numeration systems based on the hyperoperation sequence

[edit]

R. L. Goodstein[7] used the sequence of hyperoperators to create systems of numeration for the nonnegative integers. The so-calledcomplete hereditary representation of integern, at levelk and baseb, can be expressed as follows using only the firstk hyperoperators and using as digits only 0, 1, ...,b − 1, together with the baseb itself:

  • For 0 ≤nb − 1,n is represented simply by the corresponding digit.
  • Forn >b − 1, the representation ofn is found recursively, first representingn in the form
b [k]xk [k − 1]xk − 1 [k - 2] ... [2]x2 [1]x1
wherexk, ...,x1 are the largest integers satisfying (in turn)
b [k]xkn
b [k]xk [k − 1]xk − 1n
...
b [k]xk [k − 1]xk − 1 [k - 2] ... [2]x2 [1]x1n
Anyxi exceedingb − 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 baseb.

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, withX also of this form;
level-2 representations have the form b [2] X [1] Y, withX,Y also of this form;
level-3 representations have the form b [3] X [2] Y [1] Z, withX,Y,Z also of this form;
level-4 representations have the form b [4] X [3] Y [2] Z [1] W, withX,Y,Z,W also of this form;

and so on.

In this type of base-bhereditary representation, the base itself appears in the expressions, as well as "digits" from the set {0, 1, ...,b − 1}. This compares toordinary base-2 representation when the latter is written out in terms of the baseb; 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 number266, 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

[edit]

The definitions of the hyperoperation sequence can naturally be transposed toterm rewriting systems (TRS).

TRS based on definition sub 1.1

[edit]

The basic definition of the hyperoperation sequence corresponds with the reduction rules

(r1)H(0,a,b)S(b)(r2)H(S(0),a,0)a(r3)H(S(S(0)),a,0)0(r4)H(S(S(S(n))),a,0)S(0)(r5)H(S(n),a,S(b))H(n,a,H(S(n),a,b)){\displaystyle {\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 computeHn(a,b){\displaystyle H_{n}(a,b)} one can use astack, which initially contains the elementsn,a,b{\displaystyle \langle n,a,b\rangle }.

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

(r1)0,a,b(b+1)(r2)1,a,0a(r3)2,a,00(r4)(n+3),a,01(r5)(n+1),a,(b+1)n,a,(n+1),a,b{\displaystyle {\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 fromn,a,b{\displaystyle \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

ComputeH2(2,2)4{\displaystyle H_{2}(2,2)\rightarrow _{*}4}.[32]

The reduction sequence is[nb 5][nb 6]

H(S(S(0)),S(S(0)),S(S(0)))_{\displaystyle {\underline {H(S(S(0)),S(S(0)),S(S(0)))}}}
    r5H(S(0),S(S(0)),H(S(S(0)),S(S(0)),S(0))_){\displaystyle \rightarrow _{r5}H(S(0),S(S(0)),{\underline {H(S(S(0)),S(S(0)),S(0))}})}
    r5H(S(0),S(S(0)),H(S(0),S(S(0)),H(S(S(0)),S(S(0)),0)_)){\displaystyle \rightarrow _{r5}H(S(0),S(S(0)),H(S(0),S(S(0)),{\underline {H(S(S(0)),S(S(0)),0)}}))}
    r3H(S(0),S(S(0)),H(S(0),S(S(0)),0)_){\displaystyle \rightarrow _{r3}H(S(0),S(S(0)),{\underline {H(S(0),S(S(0)),0)}})}
    r2H(S(0),S(S(0)),S(S(0)))_{\displaystyle \rightarrow _{r2}{\underline {H(S(0),S(S(0)),S(S(0)))}}}
    r5H(0,S(S(0)),H(S(0),S(S(0)),S(0))_){\displaystyle \rightarrow _{r5}H(0,S(S(0)),{\underline {H(S(0),S(S(0)),S(0))}})}
    r5H(0,S(S(0)),H(0,S(S(0)),H(S(0),S(S(0)),0)_)){\displaystyle \rightarrow _{r5}H(0,S(S(0)),H(0,S(S(0)),{\underline {H(S(0),S(S(0)),0)}}))}
    r2H(0,S(S(0)),H(0,S(S(0)),S(S(0)))_){\displaystyle \rightarrow _{r2}H(0,S(S(0)),{\underline {H(0,S(S(0)),S(S(0)))}})}
    r1H(0,S(S(0)),S(S(S(0))))_{\displaystyle \rightarrow _{r1}{\underline {H(0,S(S(0)),S(S(S(0))))}}}
    r1S(S(S(S(0)))){\displaystyle \rightarrow _{r1}S(S(S(S(0))))}

When implemented using a stack, on input2,2,2{\displaystyle \langle 2,2,2\rangle }

the stack configurations    represent the equations
2,2,2_{\displaystyle {\underline {2,2,2}}}H2(2,2){\displaystyle H_{2}(2,2)}
    r51,2,2,2,1_{\displaystyle \rightarrow _{r5}1,2,{\underline {2,2,1}}}    =H1(2,H2(2,1)){\displaystyle =H_{1}(2,H_{2}(2,1))}
    r51,2,1,2,2,2,0_{\displaystyle \rightarrow _{r5}1,2,1,2,{\underline {2,2,0}}}    =H1(2,H1(2,H2(2,0))){\displaystyle =H_{1}(2,H_{1}(2,H_{2}(2,0)))}
    r31,2,1,2,0_{\displaystyle \rightarrow _{r3}1,2,{\underline {1,2,0}}}    =H1(2,H1(2,0)){\displaystyle =H_{1}(2,H_{1}(2,0))}
    r21,2,2_{\displaystyle \rightarrow _{r2}{\underline {1,2,2}}}    =H1(2,2){\displaystyle =H_{1}(2,2)}
    r50,2,1,2,1_{\displaystyle \rightarrow _{r5}0,2,{\underline {1,2,1}}}    =H0(2,H1(2,1)){\displaystyle =H_{0}(2,H_{1}(2,1))}
    r50,2,0,2,1,2,0_{\displaystyle \rightarrow _{r5}0,2,0,2,{\underline {1,2,0}}}    =H0(2,H0(2,H1(2,0))){\displaystyle =H_{0}(2,H_{0}(2,H_{1}(2,0)))}
    r20,2,0,2,2_{\displaystyle \rightarrow _{r2}0,2,{\underline {0,2,2}}}    =H0(2,H0(2,2)){\displaystyle =H_{0}(2,H_{0}(2,2))}
    r10,2,3_{\displaystyle \rightarrow _{r1}{\underline {0,2,3}}}    =H0(2,3){\displaystyle =H_{0}(2,3)}
    r14{\displaystyle \rightarrow _{r1}4}    =4{\displaystyle =4}

TRS based on definition sub 1.2

[edit]

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

(r6)H(S(0),0,a,b)S(b)(r7)H(S(0),S(0),a,0)a(r8)H(S(0),S(S(0)),a,0)0(r9)H(S(0),S(S(S(n))),a,0)S(0)(r10)H(S(0),S(n),a,S(b))H(S(b),n,a,H(S(0),S(n),a,0))(r11)H(S(S(x)),n,a,b)H(S(0),n,a,H(S(x),n,a,b)){\displaystyle {\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 isassociative, instead of rule r11 one can define

(r12)H(S(S(x)),n,a,b)H(S(x),n,a,H(S(0),n,a,b)){\displaystyle {\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 ofHn(a,b)=Hn1(a,b){\displaystyle H_{n}(a,b)=H_{n}^{1}(a,b)} can be implemented using a stack.

Initially the stack contains the four elements1,n,a,b{\displaystyle \langle 1,n,a,b\rangle }.

Then, until termination, four elements are popped and replaced according to the rules[nb 5]

(r6)1,0,a,b(b+1)(r7)1,1,a,0a(r8)1,2,a,00(r9)1,(n+3),a,01(r10)1,(n+1),a,(b+1)(b+1),n,a,1,(n+1),a,0(r11)(x+2),n,a,b1,n,a,(x+1),n,a,b{\displaystyle {\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 from1,n,a,b{\displaystyle \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

ComputeH3(0,3)0{\displaystyle H_{3}(0,3)\rightarrow _{*}0}.

On input1,3,0,3{\displaystyle \langle 1,3,0,3\rangle } the successive stack configurations are

1,3,0,3_r103,2,0,1,3,0,0_r93,2,0,1_r111,2,0,2,2,0,1_r111,2,0,1,2,0,1,2,0,1_r101,2,0,1,2,0,1,1,0,1,2,0,0_r81,2,0,1,2,0,1,1,0,0_r71,2,0,1,2,0,0_r81,2,0,0_r80.{\displaystyle {\begin{aligned}&{\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{aligned}}}

The corresponding equalities are

H3(0,3)=H23(0,H3(0,0))=H23(0,1)=H2(0,H22(0,1))=H2(0,H2(0,H2(0,1))=H2(0,H2(0,H1(0,H2(0,0))))=H2(0,H2(0,H1(0,0)))=H2(0,H2(0,0))=H2(0,0)=0.{\displaystyle {\begin{aligned}&H_{3}(0,3)=H_{2}^{3}(0,H_{3}(0,0))=H_{2}^{3}(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{aligned}}}

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

(r12)(x+2),n,a,b(x+1),n,a,1,n,a,b{\displaystyle {\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

1,3,0,3_r103,2,0,1,3,0,0_r93,2,0,1_r122,2,0,1,2,0,1_r102,2,0,1,1,0,1,2,0,0_r82,2,0,1,1,0,0_r72,2,0,0_r121,2,0,1,2,0,0_r81,2,0,0_r80{\displaystyle {\begin{aligned}&{\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{aligned}}}

The corresponding equalities are

H3(0,3)=H23(0,H3(0,0))=H23(0,1)=H22(0,H2(0,1))=H22(0,H1(0,H2(0,0)))=H22(0,H1(0,0))=H22(0,0)=H2(0,H2(0,0))=H2(0,0)=0{\displaystyle {\begin{aligned}&H_{3}(0,3)=H_{2}^{3}(0,H_{3}(0,0))=H_{2}^{3}(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{aligned}}}

Remarks

  • H3(0,3)=0{\displaystyle H_{3}(0,3)=0} is a special case, see§ Special cases above.[nb 3]
  • The computation ofHn(a,b){\displaystyle H_{n}(a,b)} according to the rules {r6 - r10, r11} is heavily recursive. The culprit is the order in which iteration is executed:Hn(a,b)=H(a,Hn1(a,b)){\displaystyle H^{n}(a,b)=H(a,H^{n-1}(a,b))}. The firstH{\displaystyle H} disappears only after the whole sequence is unfolded. For instance,H4(2,4){\displaystyle H_{4}(2,4)} converges to 65536 in 2863311767 steps, the maximum depth of recursion[nb 7] is 65534.
  • The computation according to the rules {r6 - r10, r12} is more efficient in that respect. The implementation of iterationHn(a,b){\displaystyle H^{n}(a,b)} asHn1(a,H(a,b)){\displaystyle H^{n-1}(a,H(a,b))} mimics the repeated execution of a procedure H.[nb 8] The depth of recursion, (n+1), matches the loop nesting.Meyer & Ritchie (1967) formalized this correspondence. The computation ofH4(2,4){\displaystyle 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 ofH3(0,3){\displaystyle 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

[edit]

Notes

[edit]
  1. ^ Sequences similar to thehyperoperation sequence have historically been referred to by many names, including: theAckermann function[1] (3-argument), theAckermann hierarchy,[4] theGrzegorczyk hierarchy[5][6] (which is more general),Goodstein's version of the Ackermann function,[7]operation of the nth grade,[8]z-fold iterated exponentiation of x with y,[9]arrow operations,[10]reihenalgebra[11] andhyper-n.[1][11][12][2][13]
  2. ^abcLetx =a[n](−1). By the recursive formula,a[n]0 =a[n − 1](a[n](−1)) ⇒ 1 =a[n − 1]x. One solution isx = 0, becausea[n − 1]0 = 1 by definition whenn ≥ 4. This solution is unique becausea[n − 1]b > 1 for alla > 1,b > 0 (proof by recursion).
  3. ^abcFor more details, seePowers of zero orZero to the power of zero.
  4. ^abOrdinal addition is not commutative; seeordinal arithmetic for more information
  5. ^abcThis implements theleftmost-innermost (one-step) strategy.
  6. ^In eachstep the underlinedredex is rewritten.
  7. ^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.[33]
  8. ^LOOPnTIMES DO H.

References

[edit]
  1. ^abcGeisler 2003.
  2. ^abRobbins 2005.
  3. ^Rubtsov & Romerio 2005.
  4. ^Friedman 2001.
  5. ^Campagnola, Moore & Félix Costa 2002.
  6. ^Wirz 1999.
  7. ^abcdeGoodstein 1947.
  8. ^abcdBennett 1915.
  9. ^abBlack 2009.
  10. ^Littlewood 1948.
  11. ^abcMüller 1993.
  12. ^Munafo 1999a.
  13. ^abGalidakis 2003.
  14. ^Townsend 2016.
  15. ^Romerio 2008.
  16. ^Conway, John Horton;Guy, Richard (1996),The Book of Numbers, Springer, p. 61,ISBN 9780387979939.
  17. ^abAckermann 1928.
  18. ^abcMunafo 1999b.
  19. ^Cowles & Bailey 1988.
  20. ^Knuth 1976.
  21. ^Zwillinger 2002.
  22. ^Weisstein 2003.
  23. ^Hilbert 1926.
  24. ^Nambiar 1995.
  25. ^abDoner & Tarski 1969.
  26. ^Clenshaw & Olver 1984.
  27. ^Holmes 1997.
  28. ^Zimmermann 1997.
  29. ^Pinkiewicz, Holmes & Jamil 2000.
  30. ^Doner & Tarski 1969, Definition 1.
  31. ^Doner & Tarski 1969, Theorem 3(iii).
  32. ^Bezem, Klop & De Vrijer 2003.
  33. ^Cornelius & Kirby (1975)

Bibliography

[edit]
  • Bennett, Albert A. (December 1915). "Note on an Operation of the Third Grade".Annals of Mathematics. Second Series.17 (2):74–75.doi:10.2307/2007124.JSTOR 2007124.
  • Bezem, Marc; Klop, Jan Willem; De Vrijer, Roel (2003). "First-order term rewriting systems".Term Rewriting Systems by "Terese". Cambridge University Press. pp. 38–39.ISBN 0-521-39115-6.
  • Weisstein, Eric W. (2003).CRC concise encyclopedia of mathematics, 2nd Edition. CRC Press. pp. 127–128.ISBN 1-58488-347-2.
  • Zwillinger, Daniel (2002).CRC standard mathematical tables and formulae, 31st Edition. CRC Press. p. 4.ISBN 1-58488-291-3.
Primary
Leftinverse
Rightinverse
Related
articles
Examples
in
numerical
order
Expression
methods
Notations
Operators
Related
articles
(alphabetical
order)
Retrieved from "https://en.wikipedia.org/w/index.php?title=Hyperoperation&oldid=1336266310"
Categories:
Hidden categories:

[8]ページ先頭

©2009-2026 Movatter.jp