利用者:Flightbridge/sandbox/クヌースの矢印表記

クヌースの矢印表記（クヌースのやじるしひょうき、英: Knuth's up-arrow notation）とは、1976年にドナルド・クヌースが巨大数を表記するために導入した表記法であり、アッカーマン関数およびハイパー演算子と密接な関係をもつ。この表記の考え方は、乗法が加法の反復であって冪乗が乗法の反復であることに基づいたものであり、続けて得られる冪の反復（テトレーション）および残りのハイパー演算列は通常クヌースの矢印表記を用いて記述される。

導入

通常の算術演算（加法、乗法、冪）は、以下のようにしてハイパー演算の列へと自然に拡張することができる。

自然数による乗法は、加法の反復によって定義できる。

$a\times b=\underbrace {a+a+\cdots +a} _{b}$

自然数 b を指数とする冪は、乗法の反復によって定義できる。これはクヌースの矢印表記では一本の上向き矢印で表記される。

$a\uparrow b=\underbrace {a\times a\times \cdots \times a} _{b}$

例として、グーゴルプレックス 10¹⁰¹⁰⁰ は矢印演算子を用いて 10 ↑ 10 ↑ 100 と表記できる。

以上の一連の演算を冪より先へ拡張するべく、クヌースは「二重矢印」演算子を冪の反復（テトレーション）の表記として定義した。

$a\uparrow \uparrow b={^{b}a}=\underbrace {a\uparrow a\uparrow \cdots \uparrow a} _{b}$

これらの値の評価は右から左へと行われるため、クヌースの矢印演算子は（冪と同様に）右結合なものとして定義される。

この定義による計算例は次のようになる。

$3\uparrow \uparrow 2=3^{3}=27$

$3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7625597484987$

$3\uparrow \uparrow 4=3^{3^{3^{3}}}=3^{3^{27}}=3^{7625597484987}\approx 1.2580143\times 10^{3638334640024}$

$3\uparrow \uparrow 5=3^{3^{3^{3^{3}}}}=3^{3^{3^{27}}}=3^{3^{7625597484987}}$

etc.

この時点で導かれる数は既にかなり巨大なものとなっている。だがクヌースはこれに飽き足らず、さらに「三重矢印」演算子をテトレーションの反復（ペンテーション）の表記として定義した。

$a\uparrow \uparrow \uparrow b=\underbrace {a\uparrow \uparrow a\uparrow \uparrow \cdots \uparrow \uparrow a} _{b}$

続けて、「四重矢印」演算子をペンテーションの反復（ヘキセーション）の表記として定義した。

$a\uparrow \uparrow \uparrow \uparrow b=\underbrace {a\uparrow \uparrow \uparrow a\uparrow \uparrow \uparrow \cdots \uparrow \uparrow \uparrow a} _{b}$

以下同様に続く。

一般に、n 重矢印演算子は n−1 重矢印演算子の反復（ただし右結合）へと展開できる。

${\begin{matrix}a\ \underbrace {\uparrow _{}\uparrow \!\!\dots \!\!\uparrow } _{n}\ b=\underbrace {a\ \underbrace {\uparrow \!\!\dots \!\!\uparrow } _{n-1}\ (a\ \underbrace {\uparrow _{}\!\!\dots \!\!\uparrow } _{n-1}\ (\dots \ \underbrace {\uparrow _{}\!\!\dots \!\!\uparrow } _{n-1}\ a))} _{b}\end{matrix}}$

具体例を挙げると、14 ↑↑↑↑ 4 = 14 ↑↑↑ 14 ↑↑↑ 14 ↑↑↑ 14 である。

n 重矢印演算 a ↑↑…↑ b の表記には、a ↑ⁿ b という表記がよく用いられる。この n 重矢印演算 a ↑ⁿ b はハイパー演算 a [n+2] b に等しい。ここで注意点として、39 ↑↑ 14 はあくまで 39 [4] 14 に等しく 39 [2] 14 (= 39 × 14 = 546) ではない。同様に、77 ↑⁷⁷ 77 は 77 [79] 77 に等しく 77 [77] 77 ではない。

一般化

表す数の大きさによっては矢印を何個も書くのが大変になることがある。その場合は n 重矢印演算子 ↑ⁿ （この表記は矢印の数を変数にすることができる）、またはハイパー演算子を用いると便利である。

また、場合によってはこれらの表記ですら大変になることがある。その場合はコンウェイのチェーン表記を用いると便利である。長さが3のチェーンは先の表記と同値だが、さらにチェーンを伸ばすことでより強力になる。

${\begin{matrix}a\uparrow ^{n}b&=&a[n+2]b&=&a\to b\to n\\{\mbox{(Knuth)}}&&{\mbox{(hyperoperation)}}&&{\mbox{(Conway)}}\end{matrix}}$

定義

クヌースの矢印表記は、形式的には次のように定義される。

$a\uparrow ^{n}b={\begin{cases}1,&{\mbox{if }}b=0\\a^{b},&{\mbox{if }}n=1\\a\uparrow ^{n-1}\left(a\uparrow ^{n}\left(b-1\right)\right),&{\mbox{otherwise}}\end{cases}}$

ただし a および b ≥ 0, n ≥ 0 は任意の整数である。

この定義では乗法が基本演算 (a ↑⁰ b = ab) となっており、ここから乗法の反復として冪乗 (a ↑¹ b = a ↑ b = a^b) が得られ、冪乗の反復としてテトレーション (a ↑² b = a ↑↑ b) が得られるというように続く。これは後続数関数と加法が無いことを除けば、ハイパー演算列と同値である。この定義に後続数関数と加法を含める場合、新たに初期値を追加する必要があるためやや複雑になる。

全ての矢印演算子（通常の冪乗 a ↑ b を含む）は右結合である。そのため、b ≥ 1, n ≥ 1 について次のようになる。

${\begin{aligned}a\uparrow ^{n}b&=\underbrace {a\uparrow ^{n-1}a\uparrow ^{n-1}\cdots a\uparrow ^{n-1}a} _{b}\\&=\underbrace {a\uparrow ^{n-1}a\uparrow ^{n-1}\cdots a\uparrow ^{n-1}a\uparrow ^{n-1}} _{b}\;1\\&=(a\uparrow ^{n-1})^{b}\;1\end{aligned}}$

ここで各 a はそれぞれ矢印演算子の左側に表れる（矢印演算子は非可換であるためこれは重要である）、また関数 f(x) = a ↑^m x の b 回反復合成を (a ↑^m)^b と表した。すると (a ↑^m)⁰ n = n が成り立つことから、これを用いて矢印表記の定義をより簡潔にすることができる。

$a\uparrow ^{n}b={\begin{cases}ab,&{\mbox{if }}n=0\\\left(a\uparrow ^{n-1}\right)^{b}1,&{\mbox{if }}n\geq 1\end{cases}}$

ただし a および b ≥ 0, n ≥ 0 は任意の整数である。

値の表

2 ↑^m n の計算

2 ↑^m n の計算は無限表を用いて行うことができる。まず 2ⁿ を表の最初の行に並べ、次に最初の列を 2 で埋める。その他の (m, n) には、左隣の値を p として直前の行の p 列目の値を入れていく。

2 ↑^m n の値の表

	1	2	3	4	5	6	$\cdots$	n
1	2	4	8	16	32	64	$\cdots$	2n
2	2	4	16	65536	265 536 ≈ 2.0 × 1019 728		$\cdots$	22 ↑2 (n−1)
3	2	4	65536	65 5362			$\cdots$	2 ↑2 2 ↑3 (n−1)
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\ddots$	$\vdots$
m	2	4	2 ↑m−1 4	2 ↑m−1 2 ↑m 3	2 ↑m−1 2 ↑m 4	2 ↑m−1 2 ↑m 5	$\cdots$	2 ↑m−1 2 ↑m (n−1)

この表は、m, n の値を適当にずらしたのち全ての値から 3 を引くとアッカーマン関数の値の表になる。

3 ↑^m n の計算

まず 3ⁿ を表の最初の行に並べ、次に最初の列を 3 で埋める。その他の部分には、左隣の値を p として直前の行の p 列目の値を入れていく。

3 ↑^m n の値の表

	1	2	3	4	5	$\cdots$	n
1	3	9	27	81	243	$\cdots$	3n
2	3	27	7 625 597 484 987	37 625 597 484 987		$\cdots$	33 ↑2 (n−1)
3	3	7 625 597 484 987	7 625 597 484 9873			$\cdots$	3 ↑2 3 ↑3 (n−1)
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\ddots$	$\vdots$
m	3	3 ↑m−1 3	3 ↑m−1 3 ↑m 2	3 ↑m−1 3 ↑m 3	3 ↑m−1 3 ↑m 4	$\cdots$	3 ↑m−1 3 ↑m (n−1)

10 ↑^m n の計算

まず 10ⁿ を表の最初の行に並べ、次に最初の列を 10 で埋める。その他の部分には、左隣の値を p として直前の行の p 列目の値を入れていく。

10 ↑^m n の値の表

	1	2	3	4	$\cdots$	n
1	10	100	1 000	10 000	$\cdots$	10n
2	10	10 000 000 000	1010 000 000 000		$\cdots$	1010 ↑2 (n−1)
3	10	1010			$\cdots$	10 ↑2 10 ↑3 (n−1)
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\ddots$	$\vdots$
m	10	10 ↑m−1 10	10 ↑m−1 10 ↑m 2	10 ↑m−1 10 ↑m 3	$\cdots$	10 ↑m−1 10 ↑m (n−1)

ここで、2 ≤ n ≤ 9 における 10 ↑^m n の大小は m を最上位とする辞書式順序となっているため、これら8列については単純に左上から右下へと値が大きくなっていく。

ハイパー演算列に基づいた数の表記体系

グッドスタインはハイパー演算子列を使用した非負整数の表記体系を作った。ただし彼がハイパー演算子に用いた表記はクヌースの矢印表記ではなく、ハイパー演算子 +, ×, ↑, ↑↑, … をそれぞれ角括弧を用いて [1], [2], [3], [4], … とする表記を用いた。

ここで整数 n に対し底を b とする k 階完全遺伝表現とは、最初の k 個のハイパー演算子と 0 から b−1 までの「数字」のみを用いて、以下のように表されるものである。

• 0 ≤ n ≤ b−1 のとき、単純に n は対応する「数字」によって表現される。
• n > b−1 のとき、n の表現は再帰的に求められる。まず、n の表現を次のようにおく。

$n=b[k]x_{k}[k-1]x_{k-1}[k-2]x_{k-2}\cdots [2]x_{2}[1]x_{1}$