- チェーン表記もご覧ください。
| 矢印表記 | |
|---|---|
| 型 | 3変数 |
| 基本関数 | 冪乗 |
| 急増加関数 | \(f_{\omega}(n)\) |
矢印表記 (Arrow notation) または上矢印表記 (up-arrow notation) は、広く使われているハイパー演算子の記法で、1976年にドナルド・クヌースにより巨大数を表わすために考えられた[1]。以下のルールで定義される。
\begin{align*} a \uparrow^1 b &= a^b, \\ a \uparrow^n 1 &= a, \\ a \uparrow^{n + 1} (b + 1) &= a \uparrow^n (a \uparrow^{n + 1} b). \end{align*}
\(a \uparrow^{n} b\) は \(a \uparrow\cdots\uparrow b\) （上矢印がn本）を縮めて記述したものである（nは正の整数）。n=0のとき、乗算に落とされる（\(a\uparrow^0 b = a\times b \)）。 矢印表記は右結合であり、\(a \uparrow b \uparrow c\)は常に\(a \uparrow (b \uparrow c)\)を意味する。
\(a \uparrow b\)は冪乗、\(a \uparrow\uparrow b\)はテトレーション、\(a \uparrow\uparrow\uparrow b\)はペンテーション、などである。ASCII文字では、これらをa^b, a^^b, a^^^b, ...と表記する。
矢印表記は、さらに他の表記へと一般化されている。注目すべきものとして、チェーン表記と有名な BEAFやバードの配列表記がある。
なお、矢印表記のことが「タワー表記」と書かれていることがある。指数タワー、パワータワー (Power tower) [2]という用語は指数が塔のように高く連なるテトレーションのことを意味しているので、ペンテーション以上の矢印表記を「タワー表記」と書くのは、あまり適切な訳ではないと思われる。
計算例[]
- \(2 \uparrow 3 = 2^3 = 8\)
- \(5 \uparrow 6 = 5^6 = 15625\)
- \(10 \uparrow 100 = 10^{100} =\) グーゴル
- \(3 \uparrow\uparrow 4 = 3 \uparrow 3 \uparrow 3 \uparrow 3 = 3 \uparrow 3 \uparrow 27 = 3^{7625597484987}\)
- \(5 \uparrow\uparrow 3 = 5 \uparrow 5 \uparrow 5 = 5^{5^5}\)
- \(2 \uparrow\uparrow\uparrow 2 = 2 \uparrow\uparrow 2 = 2 \uparrow 2 = 2^2 = 4\)
- \(3 \uparrow\uparrow\uparrow 2 = 3 \uparrow\uparrow 3 = 3 \uparrow 3 \uparrow 3 = 3^{3^3} = 3^{27} = 7625597484987\)
- \(2 \uparrow\uparrow\uparrow 3 = 2 \uparrow\uparrow 2 \uparrow\uparrow 2 = 2 \uparrow\uparrow 4 = 2 \uparrow 2 \uparrow 2 \uparrow 2 = 2 \uparrow 2 \uparrow 4 = 2 \uparrow 16 = 65536\)
実数への拡張[]
フィッシュは\(x > 0, n \ge 1, n \in \mathbb{N}\)に対して以下の定義をした[3]。
\begin{equation} a \uparrow^n x = \begin{cases} a^x & \text{if } 0 < x \le 1 \text{ or } n=1 \\ a \uparrow^{n-1} (a \uparrow^n (x-1)) & \text{if } 1 < x, 1 < n \end{cases} \end{equation}
この定義によれば
\begin{align*} 10^{100} &= 10 \uparrow 10 \uparrow 2 = 10 \uparrow 10 \uparrow 10 \uparrow \log_{10}(2) \\ &\approx 10 \uparrow 10 \uparrow 10 \uparrow 0.301 = 10 \uparrow \uparrow 2.301 \\ 10^{10^{100}} &= 10 \uparrow 10 \uparrow 10 \uparrow 2 \approx 10 \uparrow 10 \uparrow 10 \uparrow 10 \uparrow 0.301 = 10 \uparrow \uparrow 3.301 \\ 3 \uparrow \uparrow \uparrow 3 &= 3 \uparrow \uparrow 7625597484987 \\ &\approx 10 \uparrow \uparrow 7625597484986.041 \\ &\approx 10 \uparrow \uparrow 10 \uparrow 12.88227 \\ &\approx 10 \uparrow \uparrow 10 \uparrow 10 \uparrow 10 \uparrow 0.04532 \\ &= 10 \uparrow \uparrow 10 \uparrow \uparrow 2.04532 \\ &\approx 10 \uparrow \uparrow 10 \uparrow \uparrow 10 \uparrow \uparrow 0.31076 \\ &= 10 \uparrow \uparrow \uparrow 2.31076 \\ \end{align*}
フィッシュはこの方法を急増加関数を正確に近似するために使い、そのプログラムを公開した[4]。いくつかの例を示す。
- \(f_3(10) \approx 10 \uparrow \uparrow 10.542750880844022\)
- \(f_3(100) \approx 10 \uparrow \uparrow 101.17592742879957\)
- \(f_4(5) \approx 10 \uparrow\uparrow\uparrow 5.718488944632594\)
- \(f_4(10) \approx 10 \uparrow\uparrow\uparrow 11.00425948512775\)
- \(f_4(100) \approx 10 \uparrow\uparrow\uparrow 101.11465471078382\)
- \(f_5(100) \approx 10 \uparrow^4 101.04713294995302\)
- \(f_{10}(10) \approx 10 \uparrow^9 11.000050551171205\)
- \(f_{100}(100) \approx 10 \uparrow^{99} 101\)
チューリング機械コード[]
Input form: to represent \(a \uparrow^{c} b\), place a 1's, then c+2 ^'s, then b 1's. 例として、111^^^^^111はトリトリになります。
Turing machine code
0 * * r 0
0 _ _ l 1
1 1 _ l 2
2 ^ _ l 3
2 1 1 l 4
3 ^ _ l 3
3 1 _ l 2
4 1 1 l 4
4 ^ 1 l 4'
4 _ 1 l halt
4' ^ ^ l 5
4' 1 1 r 0
5 ^ ^ l 5
5 1 1 r 6
6 ^ x r 7
6 1 y r 9
6 | ^ l 12
7 * * r 7
7 _ | r 8
7 | | r 8
8 * * r 8
8 _ ^ l 11
9 * * r 9
9 | | r 10
10 * * r 10
10 _ 1 l 11
11 * * l 11
11 x ^ r 6
11 y 1 r 6
12 * * l 12
12 ^ ^ l 12'
12' ^ ^ l 12'
12' * * l 13
12' 1 x r 14
13 * * l 13
13 ^ ^ r 20
13 _ _ r 20
13 1 x r 14
14 * * r 14
14 ^ ^ r 15
15 ^ ^ r 15
15 x x r 16
15 1 x l 12
16 x x r 16
16 1 x l 12
16 ^ x r 17
17 ^ ^ r 17
17 1 ^ r 18
18 ^ 1 r 17
18 1 1 r 18
18 _ 1 l 19
19 * * l 19
19 x x l 12
20 x 1 r 20
20 ^ ^ r 21
21 ^ ^ r 21
21 x x r 22
22 x x r 22
22 1 _ r 23
22 ^ ^ l 30
23 1 _ r 23
23 ^ ^ l 24
24 _ ^ r 25
25 ^ ^ r 25
25 1 1 l 26
26 ^ 1 r 27
27 1 1 r 27
27 _ _ l 28
28 1 _ l 29
29 * * l 29
29 _ ^ r 25
29 x 1 l 30
30 x 1 l 30
30 ^ ^ r 31
31 * * r 31
31 _ _ l 32
32 1 _ l 1
プログラム[]
矢印表記の計算を実行するプログラム[5]が書かれている。
出典[]
- ↑ Arrow Notation from Wolfram Mathworld
- ↑ Power Tower - Mathworld
- ↑ Fish, ユーザーブログ:Kyodaisuu/テトレーションの連続関数化 2014/06/22
- ↑ Fish. Approximation of FGH with arrow notation 2023-12-05.
- ↑ [1]