巨大数研究 Wiki
登録
Advertisement
チェーン表記もご覧ください。
矢印表記
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\)
  • \(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]が書かれている。

出典[]

関連項目[]

Advertisement