ハイパーオペレーション

1928年、ヴィルヘルム・アッカーマンは3引数関数を定義した。${\displaystyle \phi (a,b,n)}$これは徐々に進化して、アッカーマン関数として知られる2引数関数になった。${\displaystyle \phi }$彼の初期条件は、現代のハイパーオペレーションとはあまり似ていなかった。${\displaystyle \phi (a,0,n)=a}$n > 2のすべての場合について。また、 n = 0に加算、 n = 1 に乗算、n = 2 にべき乗を割り当てたため、初期条件によって、4 乗以降の演算が大きく異なることになります。

使用されているもう1つの初期条件は${\displaystyle A(0,b)=2b+1}$（底が一定の場合）${\displaystyle a=2}$これは、ローザ・ペーターによるもので、ハイパーオペレーション階層を形成しません。

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

これらのハイパー演算の代替手段は、左から右への評価によって得られる。^{[ 11 ]}

${\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)}b=\left(a_{(n)}(b-1)\right)_{(n-1)}a}$

と

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

これはドナーとタルスキによって序数に拡張されました。 ^{[ 30 ]}彼らは加算にインデックス 1 ではなくインデックス 0 を使用します。彼らは上記のb − 1をbより小さいすべての序数の上限に置き換えることで、直前の順序数を持たない各序数も処理するように式を拡張し、 nも同様に扱います。ギリシャ文字を使用して、これらが単なる自然数ではなく序数であることを示します。

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

これらの定義により${\displaystyle O_{0}}$⁠追加、 ⁠${\displaystyle O_{1}}$は乗算であり、${\displaystyle O_{2}}$は指数計算です。しかし、${\displaystyle O_{3}}$⁠は、対応する（非下位の）ハイパーオペレーションで明らかになる「パワータワー」を形成することに失敗します。 ^{[ 31 ] [ nb4 ]}代わりに、

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

可換ハイパー演算は、アルバート・ベネットによって1914年には既に検討されており^{[ 8 ]} 、これはおそらくハイパー演算シーケンスに関する最も初期の記述である。可換ハイパー演算は再帰規則によって定義される。

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

これは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}}}$

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

そして、不可能になるまで繰り返し、3 つの要素がルールに従って取り出され、置き換えられます^{[ nb 5 ]}

${\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 します。 }

例

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

還元シーケンスは^{[ nb 5 ] [ nb 6 ]です}

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

反復を用いた定義は、異なる一連の削減規則につながる。

${\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 つの要素がルールに従って取り出され、置き換えられます^{[ nb 5 ]}

${\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 ]}
• 計算${\displaystyle H_{n}(a,b)}$ルールによれば、{r6 - r10, r11} は再帰性が非常に高い。原因は反復処理の実行順序にある​​。${\displaystyle H^{n}(a,b)=H(a,H^{n-1}(a,b))}$。 最初${\displaystyle H}$全体のシーケンスが展開された後にのみ消えます。たとえば、${\displaystyle H_{4}(2,4)}$2863311767ステップで65536に収束し、再帰の最大深度^{[ nb 7 ]}は65534です。
• ルール{r6 - r10, r12}に従った計算は、その点においてより効率的である。反復の実装${\displaystyle H^{n}(a,b)}$として${\displaystyle H^{n-1}(a,H(a,b))}$は、手続き H の繰り返し実行を模倣します。^{[ nb 8 ]}再帰の深さ (n+1) は、ループのネストと一致します。MeyerとRitchie (1967)はこの対応関係を形式化しました。${\displaystyle H_{4}(2,4)}$ルール{r6-r10, r12}によれば、65536に収束するには2863311767ステップが必要ですが、ハイパー演算シーケンスの5番目の演算子がテトレーションであるため、再帰の最大深度は5のみです。
• 上記の考察は再帰の深さのみに関するものです。どちらの反復方法でも、同じ数の削減ステップが発生し、同じルールが適用されます（ルール r11 と r12 が「同じ」とみなされる場合）。例が示すように、削減は${\displaystyle H_{3}(0,3)}$9ステップで収束します：1 × r7、3 × r8、1 × r9、2 × r10、2 × r11/r12。反復法は、還元規則が適用される順序のみに影響します。