ハイパーオペレーション

Generalization of addition, multiplication, exponentiation, tetration, etc.

数学において、ハイパーオペレーション列^{[注 1]とは、}単項演算（n = 0の後継関数）で始まる算術演算（この文脈ではハイパーオペレーションと呼ばれる）の無限列^{[1] [11] [13]である。この列は、}加算（n = 1）、乗算（n = 2）、べき乗（n = 3）という二項演算へと続く。

その後、このシーケンスは右結合法則を使用して、指数を超えるさらに詳細な二項演算に進みます。指数を超える演算では、このシーケンスのn番目の要素は、ルーベン グッドスタインによって、ギリシャ語の接頭辞nに-ationを接尾辞として付けて命名されており(テトレーション( n = 4)、ペンテーション( n = 5)、ヘキサレーション ( n = 6) など) ^{[5] 、}クヌースの上矢印記法でn − 2 個の矢印を使用して記述できます。各ハイパー演算は、前のハイパー演算の観点から再帰的に次のように理解できます。

${\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}$

これは、定義の再帰規則の部分に従って定義されることもあり、例えば、クヌースの上矢印バージョンのアッカーマン関数のように定義されることもある。

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

これを使うと、スキューズ数やグーゴルプレックス数など、科学的記数法では表せないほど大きな数を簡単に表示することができます（例えば、はスキューズ数やグーゴルプレックス数よりもはるかに大きいです）。しかし、グラハム数やTREE(3)など、科学的記数法でも簡単には表せない数もあります。^[14] ${\displaystyle 50[50]50}$

この再帰規則は、ハイパー演算の多くのバリエーションに共通です。

意味

定義、最も一般的な

ハイパーオペレーションシーケンス は、次のように再帰的に定義されるバイナリオペレーションのシーケンスです。 ${\displaystyle H_{n}(a,b)\colon (\mathbb {N} _{0})^{3}\rightarrow \mathbb {N} _{0}}$ ${\displaystyle H_{n}\colon (\mathbb {N} _{0})^{2}\rightarrow \mathbb {N} _{0}}$

${\displaystyle 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\geq 3{\text{ and }}b=0\\H_{n-1}(a,H_{n}(a,b-1))&{\text{otherwise}}\end{cases}}}$

( n = 0 の場合、最初の引数を無視することで 、 2 項演算は基本的に単項演算(後続関数)に簡略化されることに注意してください。)

n = 0, 1, 2, 3の場合、この定義は、それぞれsuccessor（単項演算）、加算、乗算、累乗の基本的な算術演算を次のように再現します。

${\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\uparrow {b}=a^{b}.\end{aligned}}}$

n ≥ 3の演算は、Knuthの上矢印記法で記述できます。 ${\displaystyle H_{n}}$

では、べき乗の次の演算は何でしょうか？乗算は と定義し、べき乗は と定義しました。ですから、次の演算であるテトレーションは と定義するのが理にかなっているように思われます。つまり、3つの「a」の塔を持つことになります。同様に、(a, 3)のペンテーションは テトレーション(a, テトレーション(a, a))となり、その中に3つの「a」が含まれます。 ${\displaystyle H_{2}(a,3)=a[2]3=a\times 3=a+a+a,}$ ${\displaystyle H_{3}(a,3)=a[3]3=a\uparrow 3=a^{3}=a\times a\times a,}$ ${\displaystyle H_{4}(a,3)=a[4]3=a\uparrow \uparrow 3=\operatorname {tetration} (a,3)=a^{a^{a}},}$

${\displaystyle {\begin{aligned}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\geq 3,\\\ldots &\\\end{aligned}}}$

クヌースの表記法は、インデックスの遅れを除いて、ハイパーオペレーションシーケンス全体に一致するように、負のインデックス ≥ −2 に拡張できます。

${\displaystyle H_{n}(a,b)=a\uparrow ^{n-2}b{\text{ for }}n\geq 0.}$

ハイパーオペレーションは、後続、加算、乗算、累乗などのシーケンスにおける「次は何？」という質問に対する答えとして見ることができます。

${\displaystyle {\begin{aligned}a+b&=(a+(b-1))+1\\a\cdot b&=a+(a\cdot (b-1))\\a^{b}&=a\cdot {\bigl (}a^{(b-1)}{\bigr )}\\a[4]b&=a^{a[4](b-1)}\end{aligned}}}$

基本的な算術演算間の関係が図示されており、より高次の演算を上記のように自然に定義することができます。超演算階層のパラメータは、類似の指数項で参照されることがあります。^{[ 15]}つまり、aは基数、bは指数（または超指数）です。[12] nは階数（または等級）です。 ^[6]さらに、は「aのb番目のn乗」と読みます。例えば、は「7の9番目の四乗」と読み、は「456の789番目の123乗」と読みます。 ${\displaystyle H_{n}(a,b)}$ ${\displaystyle H_{4}(7,9)}$ ${\displaystyle H_{123}(456,789)}$

一般的に言えば、ハイパー演算とは、前のハイパー演算の反復に基づいて増加する数を複利計算する方法です。後続演算、加算、乗算、累乗の概念はすべてハイパー演算です。後続演算（xからx + 1を生成する）は最も基本的なもので、加算演算子は最終的な値を生成するために1を自身に何回加算するかを指定します。乗算は数を自身に何回加算するかを指定します。累乗は数を自身に何回乗算するかを指します。

反復を用いた定義

2変数関数fの反復を次のように定義する。

${\displaystyle 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}}}$

ハイパーオペレーションシーケンスは、反復処理によって次のように定義できる。すべての整数に対して、 ${\displaystyle x,n,a,b\geq 0,}$

${\displaystyle {\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_{n}^{b+1}(a,H_{n+1}(a,0))\\H_{n}^{x+2}(a,b)&=&H_{n}(a,H_{n}^{x+1}(a,b))\end{array}}}$

反復は結合的であるため、最後の行は次のように置き換えることができる。

${\displaystyle {\begin{array}{lcl}H_{n}^{x+2}(a,b)&=&H_{n}^{x+1}(a,H_{n}(a,b))\end{array}}}$

計算

ハイパーオペレーションシーケンスの定義は、項書き換えシステム (TRS)に自然に転置できます。

定義サブ1.1に基づくTRS

ハイパーオペレーションシーケンスの基本定義は、縮約規則に対応する。

${\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}}}$

を計算するには、最初に要素を含むスタックを使用できます。 ${\displaystyle H_{n}(a,b)}$ ${\displaystyle \langle n,a,b\rangle }$

そして、不可能になるまで繰り返し、3つの要素をポップしてルールに従って置き換えます^[注2]

${\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}}}$

図式的に言えば、次のようになります: ${\displaystyle \langle n,a,b\rangle }$

スタック長 <> 1 の場合{ 3 つの要素 を POP し、 r1、r2、r3、r4、r5 の規則に従って 1 つまたは 5 つの要素をPUSH します。}

例

計算する。^[16] ${\displaystyle H_{2}(2,2)\rightarrow _{*}4}$

還元シーケンスは^{[注2] [17]}

${\displaystyle {\underline {H(S(S(0)),S(S(0)),S(S(0)))}}}$

${\displaystyle \rightarrow _{r5}H(S(0),S(S(0)),{\underline {H(S(S(0)),S(S(0)),S(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)}}))}$

${\displaystyle \rightarrow _{r3}H(S(0),S(S(0)),{\underline {H(S(0),S(S(0)),0)}})}$

${\displaystyle \rightarrow _{r2}{\underline {H(S(0),S(S(0)),S(S(0)))}}}$

${\displaystyle \rightarrow _{r5}H(0,S(S(0)),{\underline {H(S(0),S(S(0)),S(0))}})}$

${\displaystyle \rightarrow _{r5}H(0,S(S(0)),H(0,S(S(0)),{\underline {H(S(0),S(S(0)),0)}}))}$

${\displaystyle \rightarrow _{r2}H(0,S(S(0)),{\underline {H(0,S(S(0)),S(S(0)))}})}$

${\displaystyle \rightarrow _{r1}{\underline {H(0,S(S(0)),S(S(S(0))))}}}$

${\displaystyle \rightarrow _{r1}S(S(S(S(0))))}$

スタックを使用して実装する場合、入力時に ${\displaystyle \langle 2,2,2\rangle }$

スタック構成	方程式を表す
${\displaystyle {\underline {2,2,2}}}$	${\displaystyle H_{2}(2,2)}$
${\displaystyle \rightarrow _{r5}1,2,{\underline {2,2,1}}}$	${\displaystyle =H_{1}(2,H_{2}(2,1))}$
${\displaystyle \rightarrow _{r5}1,2,1,2,{\underline {2,2,0}}}$	${\displaystyle =H_{1}(2,H_{1}(2,H_{2}(2,0)))}$
${\displaystyle \rightarrow _{r3}1,2,{\underline {1,2,0}}}$	${\displaystyle =H_{1}(2,H_{1}(2,0))}$
${\displaystyle \rightarrow _{r2}{\underline {1,2,2}}}$	${\displaystyle =H_{1}(2,2)}$
${\displaystyle \rightarrow _{r5}0,2,{\underline {1,2,1}}}$	${\displaystyle =H_{0}(2,H_{1}(2,1))}$
${\displaystyle \rightarrow _{r5}0,2,0,2,{\underline {1,2,0}}}$	${\displaystyle =H_{0}(2,H_{0}(2,H_{1}(2,0)))}$
${\displaystyle \rightarrow _{r2}0,2,{\underline {0,2,2}}}$	${\displaystyle =H_{0}(2,H_{0}(2,2))}$
${\displaystyle \rightarrow _{r1}{\underline {0,2,3}}}$	${\displaystyle =H_{0}(2,3)}$
${\displaystyle \rightarrow _{r1}4}$	${\displaystyle =4}$

定義サブ1.2に基づくTRS

反復法を用いた定義は異なる縮約規則のセットを導く。

${\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}}}$

反復は結合的であるため、規則r11の代わりに次のように定義できる。

${\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}}}$

前のセクションと同様に、 の計算はスタックを使用して実装できます。 ${\displaystyle H_{n}(a,b)=H_{n}^{1}(a,b)}$

最初、スタックには 4 つの要素が含まれます。 ${\displaystyle \langle 1,n,a,b\rangle }$

そして、終了するまで、4つの要素がポップされ、規則に従って置き換えられます^[注2]

${\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}}}$

図式的に言えば、次のようになります: ${\displaystyle \langle 1,n,a,b\rangle }$

スタック長 <> 1 の場合{ 4 つの要素 を POP し、 r6、r7、r8、r9、r10、r11 の規則に従って 1 つまたは 7 つの要素をPUSH します。}

例

計算します。 ${\displaystyle H_{3}(0,3)\rightarrow _{*}0}$

入力時に連続するスタック構成は ${\displaystyle \langle 1,3,0,3\rangle }$

${\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}}}$

対応する等式は

${\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}}}$

削減規則r11を規則r12に置き換えると、スタックは次のように変換されます。

${\displaystyle {\begin{array}{lllllllll}{\text{(r12)}}&(x+2)&,n&,a&,b&\rightarrow &(x+1)&,n&,a&,1&,n&,a&,b\end{array}}}$

その後のスタック構成は

${\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}}}$

対応する等式は

${\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}}}$

備考

• ${\displaystyle H_{3}(0,3)=0}$は特別なケースです。下記を参照してください。^{[注 3]}
• の計算は、{r6 - r10, r11} という規則に従って、非常に再帰的です。問題は、反復処理の実行順序にあります。最初の は、シーケンス全体が展開された後にのみ消えます。例えば、は2863311767ステップで65536に収束しますが、再帰の最大深度^[18]は65534です。 ${\displaystyle H_{n}(a,b)}$ ${\displaystyle H^{n}(a,b)=H(a,H^{n-1}(a,b))}$ ${\displaystyle H}$ ${\displaystyle H_{4}(2,4)}$
• その点では、{r6 - r10, r12} の規則に従った計算の方が効率的です。反復処理の実装は、手続き H の繰り返し実行を模倣しています。[ ^19]再帰の深さ (n+1) はループのネストと一致します。Meyer & Ritchie (1967) はこの対応関係を形式化しました。{r6-r10, r12} の規則に従った計算も、65536 に収束するのに 2863311767 ステップかかりますが、テトレーションはハイパー演算シーケンスの 5 番目の演算子であるため、再帰の最大深さは 5 です。 ${\displaystyle H^{n}(a,b)}$ ${\displaystyle H^{n-1}(a,H(a,b))}$ ${\displaystyle H_{4}(2,4)}$
• 上記の考察は再帰の深さのみに関係しています。どちらの反復方法でも同じ数の縮約ステップが使用され、同じ規則が適用されます（規則r11とr12が「同じ」とみなされる場合）。例が示すように、縮約は9つのステップで収束します：1 X r7、3 X r8、1 X r9、2 X r10、2 X r11/r12。反復法は、縮約規則が適用される順序にのみ影響します。 ${\displaystyle H_{3}(0,3)}$

例

以下は、最初の 7 つ (0 番目から 6 番目) のハイパー演算のリストです ( 0⁰は 1 として定義されます)。

n	操作、 H n ( a , b )	意味	名前	ドメイン
0	${\displaystyle b+1}$または ${\displaystyle a[0]b}$	${\displaystyle \underbrace {1+1+1+\cdots +1+1+1} _{\displaystyle b{\mbox{ copies of 1}}}+1}$	増分、後継、ゼロ化、ハイパー0	任意
1	${\displaystyle a+b}$または ${\displaystyle a[1]b}$	${\displaystyle a+\underbrace {1+1+1+\cdots +1+1+1} _{\displaystyle b{\mbox{ copies of 1}}}}$	加算、ハイパー1
2	${\displaystyle a\times {b}}$または ${\displaystyle a[2]b}$	${\displaystyle \underbrace {a+a+a+\cdots +a+a+a} _{\displaystyle b{\mbox{ copies of }}a}}$	乗算、ハイパー2
3	${\displaystyle a^{b}}$または ${\displaystyle a[3]b}$	${\displaystyle \underbrace {a\times a\times a\times \;\cdots \;\times a\times a\times a} _{\displaystyle b{\mbox{ copies of }}a}}$	指数、ハイパー3	b実数、複素数への多値拡張を含む
4	${\displaystyle ^{b}a}$または ${\displaystyle a[4]b}$	${\displaystyle \underbrace {a[3](a[3](a[3](\cdots [3](a[3](a[3]a))\cdots )))} _{\displaystyle b{\mbox{ copies of }}a}}$	テトレーション、ハイパー4	a ≥ 0 または整数、b ≥ −1 の整数[注 4]（いくつかの拡張が提案されている）
5	${\displaystyle _{b}a}$または ${\displaystyle a[5]b}$	${\displaystyle \underbrace {a[4](a[4](a[4](\cdots [4](a[4](a[4]a))\cdots )))} _{\displaystyle b{\mbox{ copies of }}a}}$	ペンテーション、ハイパー5	a , b は整数 ≥ −1 [注 4]
6	${\displaystyle a[6]b}$	${\displaystyle \underbrace {a[5](a[5](a[5](\cdots [5](a[5](a[5]a))\cdots )))} _{\displaystyle b{\mbox{ copies of }}a}}$	ヘクセーション、ハイパー6

特殊なケース

H _n (0, b ) =

n = 0のときb + 1

b、n = 1の場合

0、n = 2の場合

1、n = 3、b = 0の場合^{[nb 3]}

0、n = 3かつb > 0の場合^{[nb 3]}

1、n > 3かつbが偶数（0を含む）の場合

n > 3かつbが奇数の場合、0

H _n (1, b ) =

b、n = 2の場合

1、n ≥ 3の場合

H _n ( a , 0) =

0、n = 2の場合

1、n = 0、またはn ≥ 3の場合

a、n = 1のとき

H _n ( a , 1) =

2、n = 0の場合

n = 1のとき、a + 1

a、n ≥ 2の場合

H _n ( a , a ) =

H _n+1 ( a , 2)、 n ≥ 1のとき

H _n ( a , −1) = ^{[注 4]}

n = 0、またはn ≥ 4の場合は0

a − 1、n = 1のとき

− a、n = 2のとき

⁠1/1つの⁠ 、 n = 3の場合

H _n (2, 2) =

3、n = 0の場合

4、n ≥ 1 の場合、再帰的に簡単に証明できます。

歴史

ハイパーオペレーションに関する最も初期の議論の一つは、1914年のアルバート・ベネットによるものであり、彼は可換ハイパーオペレーションの理論の一部を発展させた（下記参照）。^[6]約12年後、ヴィルヘルム・アッカーマンはハイパーオペレーション列にいくらか似た関数を定義した。 ^[20] ${\displaystyle \phi (a,b,n)}$

ルーベン・グッドスタインは1947 年の論文^{[5]で、現在では} ハイパーオペレーションと呼ばれている特定の演算シーケンスを導入し、指数関数を超える拡張演算にテトレーション、ペンテーションなどのギリシャ語名を提案しました (添え字が 4、5 などに対応するため)。 は 3 つの引数関数 (例: ) であるため、ハイパーオペレーション シーケンス全体は、元のアッカーマン関数(再帰的だが原始再帰的ではない) の一種であると考えられます。これはグッドスタインによって修正され、原始後継関数を算術の他の 3 つの基本演算 (加算、乗算、指数関数)とともに組み込み、指数関数を超えてこれらをよりシームレスに拡張したものです。 ${\displaystyle G(n,a,b)=H_{n}(a,b)}$ ${\displaystyle \phi (a,b,n)}$

オリジナルの 3 引数アッカーマン関数は、 グッドスタインのバージョンと同じ再帰規則 (つまり、ハイパー演算シーケンス) を使用しますが、2 つの点で異なります。第 1 に、 は、後続関数ではなく加算 ( n = 0)から始まり、次に乗算 ( n = 1)、累乗 ( n = 2) などとなる演算シーケンスを定義します。第 2 に、 の初期条件はとなり、累乗以降のハイパー演算と異なります。^{[7] [21] [22]}前の式のb + 1の意味は、 =であり、bは、 のbのようにオペランド("a")の数を数えるのではなく、演算子 (累乗) の数を数えることです。より高レベルの演算でも同様です。(詳細については、アッカーマン関数の記事を参照してください。) ${\displaystyle \phi }$ ${\displaystyle \phi (a,b,n)}$ ${\displaystyle \phi }$ ${\displaystyle \phi (a,b,3)=G(4,a,b+1)=a[4](b+1)}$ ${\displaystyle \phi (a,b,3)}$ ${\displaystyle a^{a^{\cdot ^{\cdot ^{\cdot ^{a}}}}}}$ ${\displaystyle a[4]b}$

表記

これはハイパー演算に使用されている表記法のリストです。

名前	表記は ${\displaystyle H_{n}(a,b)}$	コメント
クヌースの上矢印記法	${\displaystyle a\uparrow ^{n-2}b}$	Knuth [23]（n ≥ 3の場合）によって使用され、いくつかの参考書にも記載されています。[24] [25]
ヒルベルト記法	${\displaystyle \phi _{n}(a,b)}$	デイヴィッド・ヒルベルトが使用した。[26]
グッドスタイン記法	${\displaystyle G(n,a,b)}$	ルーベン・グッドスタインが使用。[5]
オリジナルのアッカーマン関数	${\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}}}$	ヴィルヘルム・アッカーマンが用いた（n ≥ 1の場合）[20]
アッカーマン・ペーター関数	${\displaystyle A(n,b-3)+3\ {\text{for }}a=2}$	これは基数2（a = 2） のハイパー演算に対応する。
ナンビア記法	${\displaystyle a\otimes ^{n-1}b}$	ナンビアーが使用（n ≥ 1の場合）[27]
上付き文字表記	${\displaystyle a{}^{(n)}b}$	ロバート・ムナフォが使用。[21]
下付き文字表記（下付きハイパー演算用）	${\displaystyle a{}_{(n)}b}$	ロバート・ムナフォによる下半身のハイパーオペレーションに使用。[21]
演算子表記（「拡張演算」用）	${\displaystyle aO_{n-1}b}$	ジョン・ドナーとアルフレッド・タルスキによって下側の超演算に使用された（n≥1の場合）。[28]
角括弧表記	${\displaystyle a[n]b}$	多くのオンライン フォーラムで使用されます。ASCII に便利です。
コンウェイ連鎖矢印記法	${\displaystyle a\to b\to (n-2)}$	ジョン・ホートン・コンウェイが使用（n ≥ 3の場合）

バリアントの開始1つの

1928年、ヴィルヘルム・アッカーマンは3引数関数を定義し、これは徐々に2引数関数へと発展し、アッカーマン関数として知られるようになりました。当初のアッカーマン関数は、初期条件がn > 2のすべてに対してから始まるため、現代のハイパー演算とは似ても似つきませんでした。また、彼はn = 0に加算、 n = 1に乗算、n = 2にべき乗を割り当てたため、テトレーション以降の演算では初期条件によって大きく異なる演算が生成されます。 ${\displaystyle \phi (a,b,n)}$ ${\displaystyle \phi }$ ${\displaystyle \phi (a,0,n)=a}$

n	手術	コメント
0	${\displaystyle F_{0}(a,b)=a+b}$
1	${\displaystyle F_{1}(a,b)=a\cdot b}$
2	${\displaystyle F_{2}(a,b)=a^{b}}$
3	${\displaystyle F_{3}(a,b)=a[4](b+1)}$	テトレーションのオフセット形式。この演算の反復はテトレーションの反復とは異なります。
4	${\displaystyle F_{4}(a,b)=(x\mapsto a[4](x+1))^{b}(a)}$	ペンテーションと混同しないでください。

使用されている別の初期条件は、 Rózsa Péterによる(基数は定数) であり、これはハイパー演算階層を形成しません。 ${\displaystyle A(0,b)=2b+1}$ ${\displaystyle a=2}$

0から始まるバリアント

1984年、CW ClenshawとFWJ Olverは、ハイパーオペレーションを用いてコンピュータの浮動小数点オーバーフローを防ぐ議論を始めました。^[29]それ以来、多くの著者^{[30] [31] [32]}が、ハイパーオペレーションを浮動小数点表現に適用することに新たな関心を寄せています。( H _n ( a , b ) はすべてb = -1 に対して定義されているため)。テトレーションについて議論する際、Clenshawらは初期条件 を仮定しました。これは、さらに別のハイパーオペレーション階層を形成します。前のバリエーションと同様に、4番目の演算はテトレーションと非常に似ていますが、1つずれています。 ${\displaystyle F_{n}(a,0)=0}$

n	手術	コメント
0	${\displaystyle F_{0}(a,b)=b+1}$
1	${\displaystyle F_{1}(a,b)=a+b}$
2	${\displaystyle F_{2}(a,b)=a\cdot b=e^{\ln(a)+\ln(b)}}$
3	${\displaystyle F_{3}(a,b)=a^{b}}$
4	${\displaystyle F_{4}(a,b)=a[4](b-1)}$	テトレーションのオフセット形式。この演算の反復は、テトレーションの反復とは大きく異なります。
5	${\displaystyle F_{5}(a,b)=\left(x\mapsto a[4](x-1)\right)^{b}(0)=0{\text{ if }}a>0}$	ペンテーションと混同しないでください。

ハイパーオペレーションを下げる

これらのハイパーオペレーションの代替は、左から右への評価によって得られる。[ ^9]

${\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}}}$

定義する（°または下付き文字を使用）

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

と

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

これをドナーとタルスキ^[33]は順序数に拡張した。

${\displaystyle {\begin{aligned}\alpha O_{0}\beta &=\alpha +\beta \\\alpha O_{\gamma }\beta &=\sup \limits _{\eta <\beta ,\xi <\gamma }(\alpha O_{\gamma }\eta )O_{\xi }\alpha \end{aligned}}}$

定義1(i)、系2(ii)、定理9から、a ≥ 2およびb ≥ 1の場合、^{[独自の研究? ]}

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

しかし、これは一種の崩壊に陥り、ハイパーオペレーターに伝統的に期待されていた「パワータワー」を形成できなかった。^{[34] [注5]}

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

α ≥ 2 および γ ≥ 2 の場合、^{[28] [系 33(i)] [注 5]}

${\displaystyle \alpha _{(1+2\gamma +1)}\beta \leq \alpha _{(1+2\gamma )}(1+3\alpha \beta ).}$

n	手術	コメント
0	${\displaystyle F_{0}(a,b)=a+1}$	増分、後継、ゼロ化
1	${\displaystyle F_{1}(a,b)=a+b}$
2	${\displaystyle F_{2}(a,b)=a\cdot b}$
3	${\displaystyle F_{3}(a,b)=a^{b}}$
4	${\displaystyle F_{4}(a,b)=a^{\left(a^{(b-1)}\right)}}$	テトレーションと混同しないでください。
5	${\displaystyle F_{5}(a,b)=\left(x\mapsto x^{x^{(a-1)}}\right)^{b-1}(a)}$	ペンテーションと混同しないでください。テトレーション に似ています。

可換超演算

可換超演算はアルバート・ベネットによって1914年に早くも考察されており^[6] 、これはおそらく超演算列に関する最も古い言及である。可換超演算は再帰規則によって定義される。

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

これはaとbに関して対称的であり、すべてのハイパー演算は可換であることを意味します。このシーケンスにはべき乗が含まれていないため、ハイパー演算階層は形成されません。

n	手術	コメント
0	${\displaystyle F_{0}(a,b)=\ln \left(e^{a}+e^{b}\right)}$	滑らかな最大値（LogSumExp）
1	${\displaystyle F_{1}(a,b)=a+b}$
2	${\displaystyle F_{2}(a,b)=a\cdot b=e^{\ln(a)+\ln(b)}}$	これは対数の特性によるものです。
3	${\displaystyle F_{3}(a,b)=a^{\ln(b)}=e^{\ln(a)\ln(b)}}$	有限体では、これはDiffie-Hellman 鍵交換操作です。
4	${\displaystyle F_{4}(a,b)=e^{e^{\ln(\ln(a))\ln(\ln(b))}}}$	テトレーションと混同しないでください。

ハイパーオペレーションシーケンスに基づく記数法

RL Goodstein ^{[5] は、}ハイパー演算子の列を用いて非負整数の記数法を構築した。レベルk、基数bにおける整数nのいわゆる完全遺伝的表現は、最初のk 個のハイパー演算子のみを用い、数字として 0, 1, ..., b − 1 のみを用い、基数b自身と合わせて以下のように表すことができる。

• 0 ≤ n ≤ b − 1 の場合、nは対応する数字で単で表される。
• n > b − 1の場合、 nの表現は再帰的に求められ、まずn を次の形式で表現する。

b [ k ] x _k [ k − 1] x _{k − 1} [ k - 2] ... [2] x ₂ [1] x ₁

ここで、x _k、...、x ₁は、（順番に）を満たす最大の整数である。

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

b − 1を超えるx i_は同じ方法で再表現され、結果の形式に数字 0、1、...、b − 1 と基数bのみが含まれるようになるまでこの手順が繰り返されます。

不要な括弧は、高レベルの演算子に評価順序で高い優先順位を与えることによって回避できます。つまり、

レベル1の表現はb [1] Xの形式を持ち、Xもこの形式である。

レベル2の表現はb [2] X [1] Yの形式を持ち、X、Yもこの形式である。

レベル3の表現はb [3] X [2] Y [1] Zの形式を持ち、X、Y、Zもこの形式である。

レベル4の表現はb [4] X [3] Y [2] Z [1] Wの形式をとり、X、Y、Z、Wもこの形式をとる。

等々。

このタイプのb進数 遺伝表現では、式の中に基数そのものだけでなく、集合 {0, 1, ..., b − 1} の「数字」も現れる。これは、通常の2 進数表現を基数bで表した場合の表現と比較できる。例えば、通常の 2 進数表記では 6 = (110) ₂ = 2 [3] 2 [2] 1 [1] 2 [3] 1 [2] 1 [1] 2 [3] 0 [2] 0 となるが、レベル 3 の 2 進数遺伝表現では 6 = 2 [3] (2 [3] 1 [2] 1 [1] 0) [2] 1 [1] (2 [3] 1 [2] 1 [1] 0) となる。遺伝的表現は、[1] 0、[2] 1、[3] 1、[4] 1などのインスタンスを省略することによって省略することができます。たとえば、上記のレベル3の2進数表現6は、2 [3] 2 [1] 2と省略されます。

例:レベル 1、2、3、4、および 5 における 数値266の一意の 2 進表現は次のとおりです。

レベル1: 266 = 2 [1] 2 [1] 2 [1] ... [1] 2 (2が133個)

レベル2: 266 = 2 [2] (2 [2] (2 [2] (2 [2] (2 [2] 2 [2] 2 [2] 2 [1] 1)) [1] 1)

レベル3: 266 = 2 [3] 2 [3] (2 [1] 1) [1] 2 [3] (2 [1] 1) [1] 2

レベル4: 266 = 2 [4] (2 [1] 1) [3] 2 [1] 2 [4] 2 [2] 2 [1] 2

レベル5: 266 = 2 [5] 2 [4] 2 [1] 2 [5] 2 [2] 2 [1] 2

参照

• 大きな数字
• 急速に成長する階層

注記

1. ハイパー演算シーケンスに類似したシーケンスは、歴史的に多くの名前で呼ばれてきました。これには、アッカーマン関数^[1] (3引数)、アッカーマン階層^[2]、グジェゴルチク階層^{[3] [4]} (より一般的なもの)、グッドスタインのアッカーマン関数バージョン^[5]、n次の演算^[6]、 xとyのz倍反復累乗^[7]、矢印演算^[8]、レイヘン代数^[9]、ハイパーn ^{[1] [9] [10] [11] [12]}などがあります。
2. これは、左端から内側への（1ステップ）戦略を実装します。
3. 詳細については、「ゼロの累乗」または「ゼロのゼロ累乗」を参照してください。
4. x = a [ n ](−1)とします。再帰式により、a [ n ]0 = a [ n − 1]( a [ n ](−1)) ⇒ 1 = a [ n − 1] xとなります。一つの解はx = 0です。なぜなら、n ≥ 4のとき、定義によりa [ n − 1]0 = 1となるからです。この解は、すべてのa > 1, b > 0に対してa [ n − 1] b > 1となるため、唯一です（再帰による証明）。
5. 順序加算は可換ではありません。詳細については順序算術を参照してください。

参考文献

1. ガイスラー 2003.
2. フリードマン 2001.
3. カンパニョーラ、ムーア、フェリックス・コスタ、2002。
4. ウィルツ 1999.
5. グッドスタイン 1947.
6. ベネット 1915.
7. ブラック 2009より。
8. リトルウッド 1948年。
9. ミュラー 1993.
10. ムナフォ 1999a.
11. ロビンズ 2005より。
12. ガリダキス 2003より。
13. ルブツォフ＆ロメリオ 2005.
14. タウンゼント 2016.
15. ロメリオ 2008.
16. ベゼム、クロップ、デ・フライエル、2003.
17. 各ステップで下線部のredexが書き換えられます。
18. 再帰の最大深度とは、ある手続きの最も深い呼び出し時に存在する、その手続きの活性化の階層数を指す。Cornelius & Kirby (1975)
19. ループ n 回実行Hを実行します。
20. アッカーマン 1928。
21. ムナフォ 1999b.
22. カウルズ＆ベイリー 1988.
23. クヌース 1976.
24. ズウィリンガー 2002.
25. ワイスタイン 2003.
26. ヒルベルト 1926.
27. ナンビア 1995.
28. Doner & Tarski 1969より。
29. クレンショー＆オルバー 1984.
30. ホームズ 1997.
31. ツィンマーマン 1997.
32. ピンキーヴィッツ、ホームズ、ジャミル 2000年。
33. Doner & Tarski 1969、定義 1.
34. Doner & Tarski 1969、定理3(iii)。

参考文献

• アッカーマン、ヴィルヘルム(1928)。 「ツム・ヒルベルトシェン・アウフバウ・デア・リーレン・ザーレン」。数学アンナレン。99 : 118–133。土井:10.1007/BF01459088。S2CID  123431274。

• ベネット、アルバート・A. (1915年12月). 「第3級の演算に関するノート」. Annals of Mathematics . 第2集. 17 (2): 74– 75. doi :10.2307/2007124. JSTOR  2007124.

• マルク・ベゼム。クロップ、ヤン・ウィレム。デ・ヴリエル、ロエル (2003)。 「一次項書き換えシステム」。「Terese」による用語書き換えシステム。ケンブリッジ大学出版局。38 ～ 39ページ 。ISBN 0-521-39115-6。

• ブラック、ポール・E. (2009年3月16日). 「アッカーマン関数」.アルゴリズムとデータ構造の辞書. 米国国立標準技術研究所 (NIST) . 2021年8月29日閲覧.

• カンパニョーラ、マヌエル・ラメイラス。クリストファー・ムーア;フェリックス・コスタ、ホセ (2002 年 12 月)。 「再帰的整数論における超有限序数」。複雑さのジャーナル。18 (4): 977–1000 .土井: 10.1006/jcom.2002.0655。

• Clenshaw, CW; Olver, FWJ (1984年4月). 「浮動小数点を超えて」. Journal of the ACM . 31 (2): 319– 328. doi : 10.1145/62.322429 . S2CID  5132225.

• コーネリアス, BJ; カービー, GH (1975). 「再帰の深さとアッカーマン関数」. BIT数値数学. 15 (2): 144– 150. doi :10.1007/BF01932687. S2CID  120532578.

• Cowles, J.; Bailey, T. (1988年9月30日). 「アッカーマン関数のいくつかのバージョン」. ワイオミング大学コンピュータサイエンス学部, ララミー, ワイオミング州. 2021年8月29日閲覧.

• ドナー、ジョン。タルスキー、アルフレッド(1969)。 「序数の拡張算術」。数学の基礎。65 : 95–127 .土井: 10.4064/fm-65-1-95-127。

• フリードマン、ハーヴェイ・M. (2001年7月). 「長有限列」.組合せ理論ジャーナル. シリーズA. 95 (1): 102– 144. doi : 10.1006/jcta.2000.3154 .

• Galidakis, IN (2003). 「数学」. 2009年4月20日時点のオリジナルよりアーカイブ。2009年4月17日閲覧。

• ガイスラー、ダニエル (2003). 「指数関数の先には何があるのか​​？」2009年4月17日閲覧。

• グッドスタイン、ルーベン・ルイス (1947年12月). 「再帰的数論における超限順序数」(PDF) . Journal of Symbolic Logic . 12 (4): 123– 129. doi :10.2307/2266486. JSTOR  2266486. S2CID  1318943.

• デイヴィッド・ヒルベルト (1926)。 「ユーバー・ダス・ウンエンドリッシェ」。数学アンナレン。95 : 161–190。土井:10.1007/BF01206605。S2CID  121888793。

• Holmes, WN (1997年3月). 「複合演算：新標準の提案」. Computer . 30 (3): 65– 73. doi :10.1109/2.573666 . 2009年4月21日閲覧。

• ドナルド・アービン・クヌース（1976年12月）. 「数学とコンピュータサイエンス：有限性への対処」 . Science . 194 (4271): 1235– 1242. Bibcode :1976Sci...194.1235K. doi :10.1126/science.194.4271.1235. PMID  17797067. S2CID  1690489. 2009年4月21日閲覧.

• Littlewood, JE (1948年7月). 「大きな数」. Mathematical Gazette . 32 (300): 163– 171. doi :10.2307/3609933. JSTOR  3609933. S2CID  250442130.

• マイヤー、アルバート・R.；リッチー、デニス・マカリスター(1967).ループプログラムの計算量. ACM '67: 1967年第22回全国会議議事録. doi : 10.1145/800196.806014 .

• Müller, Markus (1993). 「Reihenalgebra」(PDF) . 2013年12月2日時点のオリジナル(PDF)からアーカイブ。 2021年11月6日閲覧。

• Munafo, Robert (1999a). 「アッカーマン関数のバージョン」. MROBのLarge Numbers . 2021年8月28日閲覧。

• ムナフォ、ロバート (1999b). 「新しい演算子と関数の発明」. MROBにおける大きな数. 2021年8月28日閲覧。

• ナンビア, KK (1995). 「アッカーマン関数と超限順序数」.応用数学レターズ. 8 (6): 51– 53. doi : 10.1016/0893-9659(95)00084-4 .

• Perstein, Millard H. (1962年6月1日). 「アルゴリズム93：一般順序演算」. Communications of the ACM . 5 (6).ニューヨーク市: Association for Computing Machinery : 344. doi : 10.1145/367766.368160 . ISSN  0001-0782.

• Pinkiewicz, T.; Holmes, N.; Jamil, T. (2000). 「有理数のための複合演算ユニットの設計」. Proceedings of the IEEE Southeast Con 2000. 「新世紀への準備」（カタログ番号00CH37105）. Proceedings of the IEEE. pp.  245– 252. doi :10.1109/SECON.2000.845571. ISBN 0-7803-6312-4. S2CID  7738926。

• Robbins, AJ (2005年11月). 「Home of Tetration」. 2015年6月13日時点のオリジナルよりアーカイブ。2009年4月17日閲覧。

• Romerio, GF (2008年1月21日). 「ハイパーオペレーション用語集」. Tetration Forum . 2009年4月21日閲覧。

• Rubtsov, CA; Romerio, GF (2005年12月). 「アッカーマン関数と新しい算術演算」 . 2009年4月17日閲覧。

• タウンゼント、アダム (2016年5月12日). 「大きな数の名前」. Chalkdust 誌.

• ワイスタイン、エリック・W. (2003). CRC簡潔数学百科事典 第2版. CRC Press. pp.  127– 128. ISBN 1-58488-347-2。

• マルク・ヴィルツ (1999)。 「安全な再帰によるグジェゴルチク階層の特徴付け」(PDF)。ベルン: Institut für Informatik und angewandte Mathematik。CiteSeerX  10.1.1.42.3374。S2CID  117417812。

• Zimmermann, R. (1997). 「コンピュータ演算：原理、アーキテクチャ、そしてVLSI設計」(PDF) . 講義ノート、統合システム研究所、ETHチューリッヒ。 2013年8月17日時点のオリジナル(PDF)からアーカイブ。 2009年4月17日閲覧。

• ツヴィリンガー、ダニエル (2002). CRC標準数学表と公式、第31版. CRC Press. p. 4. ISBN 1-58488-291-3。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Hyperoperation&oldid=1318620996"