1. No category

巨大数論
初版 6 刷
2014 年 1 月 24 日
3 =
∧
3 3 =
3
27
3∧ 3∧ 3 ≈ 10∧ 12.88
3∧ 3∧ 3∧ 3 ≈ 10∧ 10∧ 12.56
3∧ 3∧ 3∧ 3∧ 3 ≈ 10∧ 10∧ 10∧ 12.56
3∧ 3∧ 3∧ 3∧ 3∧ 3 ≈ 10∧ 10∧ 10∧ 10∧ 12.56
3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3 ≈ 10∧ 10∧ 10∧ 10∧ 10∧ 12.56
3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3 ≈ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 12.56
3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3 ≈ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 12.56
3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3 ≈ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 12.56
3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3 ≈ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 12.56
3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3 ≈ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 12.56
3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3 ≈ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 12.56
3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3 ≈ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 12.56
3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3 ≈ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 12.56
3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3∧ 3 ≈ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 10∧ 12.56
ふぃっしゅっしゅ
3
目次
第 1 章 はじめに
4
第 2 章 原始帰納関数
6
2.1
クラス 2 の巨大数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1
2.1.2
数のクラス分け . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.3
2.1.4
グーゴル . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
無量大数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
数の比較 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
6
7
9
10
2.2
2.3
2.4
クラス 3 の巨大数 - 不可説不可説転とグーゴルプレックス . . . . . . . . . . . . . . . . . .
2.5
2.6
矢印表記とハイパー演算子 - トリトリ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
20
2.7
原始帰納関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
クラス 4 の巨大数 - 第 2 スキューズ数
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
クラス 5 以上の巨大数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
グッドスタイン数列
第 3 章 2 重帰納関数
12
13
14
25
3.1
3.2
3.3
アッカーマン関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4
3.5
グラハム数
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
コンウェイのチェーン表記 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
30
3.6
ここまでのまとめ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
2 重帰納関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
モーザー数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
第 4 章 多重帰納関数
25
27
28
33
4.1
4.2
4.3
多重帰納 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4
4.5
チェーンの長さを変数化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.6
4.7
4.8
ふぃっしゅ数バージョン 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ふぃっしゅ数バージョン 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
46
49
4.9
ここまでに出てきた巨大数の比較 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
多変数アッカーマン関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
多重帰納に見えてそうでない関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ふぃっしゅ数バージョン 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
矢印回転表記とバード数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
33
34
35
36
4
第 5 章 順序数とハーディー関数
53
53
5.1
多重帰納を超えて . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2
5.3
5.4
順序数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
カントールの標準形
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ハーディー関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
55
56
5.5
色々な関数のハーディー関数による近似 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
第 6 章 証明可能帰納関数
59
6.1
6.2
証明可能帰納関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3
6.4
6.5
ふぃっしゅ数バージョン 3 の拡張 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.6
6.7
バードの多重リスト表記 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 重リストアッカーマン関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
多重リストアッカーマン関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ふぃっしゅ数バージョン 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ヒドラゲーム . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
第 7 章 帰納関数
59
59
60
61
61
64
65
69
69
7.1
η0 以下の順序数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2
7.3
7.4
ふぃっしゅ数バージョン 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.5
7.6
さらに大きな順序数
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Taranovsky の順序数記法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
75
76
7.7
7.8
7.9
多変数 C0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ミーミーミーロッカプーワ・ウンパ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
76
77
78
7.10 その他の関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.11 帰納関数の大きさ比較 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
78
78
ヴェブレン関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Bachmann-Howard 順序数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
バード数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
第 8 章 計算不可能な関数
70
73
75
80
80
8.1
ビジービーバー関数
8.2
8.3
8.4
ふぃっしゅ数バージョン 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Xi 関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
81
82
82
8.5
ラヨ数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ビジービーバーのハーディー的拡張 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
第 1 章 はじめに
私たちが日常生活で使う大きな数は、たとえば世界の人口が 70 億人を突破したとか、国家予算が 200 兆
円であるといったように、100 兆=10 の 14 乗程度までです。その上の単位である京（けい）を知っていて
も、さらにその上の垓（がい）といった単位を使うことはめったにありません。
科学の世界では、たとえば 1 モルに含まれる要素粒子の数を表すアボガドロ数という数は、約 6023 垓に
なります。物理的に意味のある非常に大きな定数としては、エディントン数という数があります。これは、
全宇宙にこの数の陽子があるとしたもので、2 の 256 の 136 倍で、10 の 79 乗のオーダーになります。大き
な数として有名な「無量大数」という数の単位は 10 の 68 乗で、それよりもエディントン数の方が大きい
ことになります。「天文学的数字」という表現がありますが、天文学の世界でも、エディントン数よりも大
きい数を扱うことはまずありません。
ところが、それよりもさらに大きな数が、仏教の経典には書かれているとのことです。大方広仏華厳経の
巻第四十五、阿僧祇品第三十という経典に書かれている不可説不可説転という数の大きさを計算すると、10
の 37218383881977644441306597687849648128 乗というとてつもない大きな数になります1 。
「不可説不可
説転メートル」がどれくらい長い距離なのか、あるいは「不可説不可説転秒」がどれくらい長い時間なの
か、想像をすることすら不可能です。
一方、数学の世界では、不可説不可説転とは比べ物にならないほど大きなグラハム数という数が定義され
ています。これは、ギネスブックにも載ったそうです。この数の大きさは、たとえば「10 の 10 乗の 10 乗
の…と 100 回繰り返して…」といったような表現では、とても表現しきれない気の遠くなる程ほど大きな
数です。
このような巨大数について、２ちゃんねる掲示板というインターネットの掲示板でなされた議論を下敷
きに書いたものが本書です。２ちゃんねる掲示板では、話題のジャンルごとに掲示板群「板」が設定され、
板の中で話題ごとに立てられる「スレッド」において、会話がなされます。数学の話題を扱う「数学板」の
中の「巨大数探索スレッド」シリーズの中で、巨大数探索が繰り広げられてきました。
この巨大数探索スレッドに「ふぃっしゅっしゅ」という名前で書き込んでいるのが、本書の著者です。そ
こでは、グラハム数よりもはるかに大きいふぃっしゅ数という数を考案して書き込みました (2002 年 6 月 29
日)。ふぃっしゅ数は、単純に「大きい数を定義する」という目的で作られたものです。ただそれだけの、何
の実用性もない数ですが、このふぃっしゅ数をきっかけとして、巨大数をめぐる白熱した議論が戦わされま
した。
「ふぃっしゅっしゅ」とはふざけた名前ですが、当初スレッドに参加したときには、一時的なお遊び程
度に思っていたためです。まさか、ここまでまじめに数学的議論が戦わされるとは思っていませんでした。
本書は、2007 年 9 月 24 日に「まだ書きかけ」バージョンを公開し、何度か細かい修正をしましたが、ずっ
と書きかけのまま放置していました。2013 年 9 月 11 日に、裏サンデーに小林銅蟲さんによる「寿司 虚
空編」という漫画が連載開始され2 、第 1 話ではグラハム数が、第 2 話ではふぃっしゅ数が出てきました。
1 無量大数の彼方へ
http://www.sf.airnet.ne.jp/˜ts/language/largenumber.html
http://urasunday.com/u-2 09/index.html
2 裏サンデー「寿司 虚空編」
第1章
6
はじめに
小林さんは、シュールな漫画「ねぎ姉さん」3 の作者として有名な方ですが、
「巨大数探索スレッド」では、
ふぃっしゅ数が登場した時からずっと巨大数の探求をされて来た方です。最初のスレッドでは「695」スレッ
ド 2 と 3 では「旧 695」スレッド 4 以降では「もやしっ子」という名前で書き込みをされています。また、
巨大数探索スレッドでの議論をまとめた巨大数研究室のサイト4 を管理されています。著者は、小林さん主
催の巨大数勉強会に参加したこともあります。
「寿司 虚空編」の連載に触発され、この機会にある程度形にまとめようと思い、2013 年 10 月に大幅に
書き加えて初版として公開することとしました。
本書では、まずは巨大数サイトの定番、ロバート・ムナフォ氏の Large Numbers
5
のページを参考にし
ながら、無量大数や不可説不可説転等の巨大数の話から入ります。そして、クヌースの矢印表記が原始帰納
であることを示し、アッカーマン関数やモーザー数、グラハム数などを越えるコンウェイのチェーン表記が
2 重帰納であることを示してから、3 重帰納以上の多重帰納関数について説明します。そこでは、巨大数ス
レッドで生まれた多変数アッカーマン関数やふぃっしゅ数などについて説明します。そして、順序数の概念
を導入することによって、関数の増加速度を評価出来るようになり、さらに大きな巨大数の話へと発展し
ます。
改めて海外のサイトを見ると、Googology Wiki
6
といったサイトが立ち上がり、巨大数スレッドで話題
になったバード氏もさらに大きな巨大数を作成していることが分かりましたので、そこで得た最新の巨大
数情報を初版で書き加えました。2013 年 12 月には、Googology Wiki の日本語版「巨大数研究 Wiki」7 が
立ち上がり、日本語での巨大数情報整理が始められています。
著者は数字で遊ぶのは好きですが数学の専門家ではありません。大学は農学部出身で、集合論や情報理論
などの専門的な教育を受けていません。最初に「ふぃっしゅ数」を考えた時に持っていた知識は、アッカー
マン関数とグラハム数に関する解説をネットで読んだ程度のものです。本書に記されている数学的な内容
は、巨大数探索スレッドやネット上の解説ページで得た知識を元に書いていますが、素人が書いた文章なの
で、不正確な内容が含まれている可能性があります。
本書は、ホームページ8 から最新バージョンの PDF ファイルをダウンロードできます。また、改訂履歴
もホームページに記録します。本書に対するご意見ご感想、数学的な誤り、計算間違いや誤植等の指摘は、
著者のツイッターアカウント @kyodaisuu
10
ジウォール
9
へのメンション、あるいは巨大数研究 Wiki の著者のメッセー
宛にお願いします。
3 ねぎ姉さん
http://negineesan.com/
http://www.geocities.co.jp/Technopolis/9946/
5 Large Numbers (Robert Munafo) http://www.mrob.com/pub/math/largenum.html
6 Googology Wiki http://googology.wikia.com/
7 巨大数研究 Wiki http://ja.googology.wikia.com/
8 巨大数論（本書）のホームページ http://gyafun.jp/ln/
9 著者のツイッターアカウント https://twitter.com/kyodaisuu
10 巨大数探求 Wiki @kyodaisuu メッセージウォール http://ja.googology.wikia.com/wiki/Message Wall:Kyodaisuu
4 巨大数研究室
7
第 2 章 原始帰納関数
2.1
2.1.1
クラス 2 の巨大数
数のクラス分け
本章では、原始帰納関数で表現できる数を取り上げます。原始帰納関数の説明に入る前に、具体的に大
きな数について考えます。ロバート・ムナフォ氏は、Large Numbers
1
のページで、様々な巨大数につい
て紹介し、考察しています。その説明に従って、段階的に大きな数について記します。ムナフォ氏は、数の
大きさをクラス分けして、クラス 0 の数、クラス 1 の数、クラス 2 の数、クラス 3 の数…と分類しました。
日常生活で使う数は、クラス 2 の数までです。さらに、無量大数やグーゴルといった有名な巨大数も、クラ
ス 2 になります。そこで、本節ではクラス 2 の数までについて見てみます。
クラス 0 の数 (0-6) : クラス 0 は、カウフマンが提唱した subitizing という概念で2 、即座に認識出来る
数です。たとえば、１本の鉛筆があれば、それは１本であると一瞬で認識出来ます。2 本であっても、一瞬
で認識出来ます。5 本の鉛筆はどうでしょうか。目をつぶって、目を一瞬あけてすぐに閉じた時に、見た鉛
筆の本数を目を閉じた状態で言えるかとなれば、5 本くらいであれば誰でも言えるでしょう。このように、
いちいち数えなくても即座に認識可能な数は、最大 5 から 9 程度であると言われていますが、ムナフォ氏
は低めに見積もって 6 であるとして、0 から 6 までの数字がクラス 0 であるとしました。
クラス 1 の数 (6 − 106 ) : クラス 1 は、人間の目でおおまかな数が認識出来る数です。この上限を、ム
ナフォ氏は 100 万であるとしました。たとえば、大きな紙に 100 万個の点を印刷して、その 1 つ 1 つの点
を見分けながら、残りのすべての点が視野に入るようにします。ムナフォ氏の実験で本人はそれができま
したが、人によってはもっと大きな数でも認識出来るかもしれません。クラス 1 の数であれば、正確な数
は分からなくても、大体の大きさが認識出来ます。たとえば、部屋の中に 85 人の人がいれば、70∼100 人
程度かな、と分かります。もっとたくさんの人がいるときには、何千人とか何万人といった表現をします。
このように、正確な数は分からなくても、だいたいの数を認識出来る限界をクラス 1 として、ムナフォ氏
はその上限を 100 万としました。
6
クラス 2 の数 (106 − 1010 ) : クラス 2 は、10 進数で記録できる数です。クラス 0 の 6 からクラス 1 の
6
106 = 1000000 へと増やしたように、分かりやすくクラス 2 は 1010 = 101000000 までとされました。ここ
で、指数を 2 つ以上重ねた時には、右上から順番に計算する、ということに気をつける必要があります。つ
6
まり、1010 = 10(10
6
)
です。左から順番に計算すると、(1010 )6 = 1010×6 = 1060 となって、指数が掛け算
になってしまいますから、右から計算した場合と比べてとても小さい数になります。クラス 2 は、100 万桁
までの数字で記録出来る数ということです。クラス分けの境界は、全体として大ざっぱなものです。子供
1 再掲:
Large Numbers (Robert Munafo) http://www.mrob.com/pub/math/largenum.html
et al. (1949). ”The discrimination of visual number”. American Journal of Psychology 62 (4): 498-525.
http://dx.doi.org/10.2307/1418556
2 Kaufman
第 2 章 原始帰納関数
8
に「できるだけ大きな数を書いてごらん」と言って紙を渡せば、多くは「999999…」と書き続けるでしょう
（111111…と書く方が楽ですが）。根性のある子供でも 100 万桁はなかなか書き続けられないと思います。
何桁記録出来るのかは、どこにどのように記録するのかにもよります。パソコンにデータを保存するのは
簡単なので、100 万桁よりもずっと大きな桁数を保存出来ます。ここでは、紙と鉛筆でものすごく頑張れば
10 進数表記で書ける数、と解釈すると、100 万桁という上限がちょうどいい感覚になりそうです。
2.1.2
無量大数
まずは、日本での大きな数の数え方について記します。それから、その由来となった中国とインドにさか
のぼって調べたところを記します。
私達が日常生活で扱う数は、クラス 2 の数までです。したがって、日常生活で使う数字に関する言葉も、
だいたいこの範囲の言葉になります。そこでまずは、日本語での数の数え方から見ていきます。それから、
その源泉をたどって中国、インドの数について見ます。数の位は、一、十、百、千、万と 10 倍ずつになり、
その先は 1 万倍ずつ、億 = 108 、兆 = 1012 、京（けい）= 1016 、垓（がい）= 1020 、杼（じょ、この漢字は、
正しくは禾偏）= 1024 、穣（じょう）= 1028 、溝（こう）= 1032 、澗（かん）= 1036 、正（せい）= 1040 、
載（さい）= 1044 、極（ごく）= 1048 、恒河沙（ごうがしゃ）= 1052 、阿僧祇（あそうぎ）= 1056 、那由
他（なゆた）= 1060 、不可思議（ふかしぎ）= 1064 、 無量大数（むりょうたいすう）= 1068 となります。
垓以上の単位を日常生活で使うことはめったになく、特に意識しなければ知らない人も多いでしょう。著者
は、子供の頃から数字が好きだったので、父に教えてもらって無量大数までの桁を覚えて喜んでいました。
当時は無量大数は 1088 であると覚えていて、これは恒河沙から上は 108 ずつ増える万万進という方式に基
づいていたためですが、現在は万進に統一されていますので、正しくは 1068 になります。
【定義】無量大数
無量大数 = 1068
さて、高杉親知氏の作成した「無量大数の彼方へ」3 というサイトによれば、昔の中国では、後漢の時代
に載までの単位が記されていて、億以上の単位については、「下数」「中数」「上数」の３つの体系があり、
さらに「中数」には「万進」「万万進」という体系があって、合計４つの体系それぞれで、同じ言葉でも表
す数字が違っていました。下数では、次の単位では 10 倍になるため、万=104 、億=105 、兆=106 と、少し
ずつ上がり、載=1014 になります。中数では、万進では 1 万倍ずつ、万万進では 1 億倍ずつ上がります。し
たがって、万進の兆は現在の日本と同じ 1012 になるのに対して、万万進では「万億」が 1012 になります。
そして、万万進の兆は 1016 で、万進の京と同じになります。載は、万進では 1044 、万万進では 1080 になり
ます。中国では、万進と万万進が統一されずに近代化が進んだので混乱が生じましたが、日本では、万進の
表記に統一されたので混乱がありません。
下数よりも中数よりも、飛躍的に数の増加が大きいのが 上数 です。上数では、単位を 2 乗すると次の単位
3
4
になります。したがって、億=108 = 102 、万億=1012 、千万億=1015 、兆=102 = 1016 、万兆=1020 、億兆
5
=1024 、万億兆=1028 、千万億兆=1031 、京=102 = 1032 、億京=1040 、兆京=1048 、億兆京=1056 、万億兆京
6
7
8
9
=1060 、垓=102 = 1064 、千万億兆京垓=10127 、杼 = 102 = 10128 、穣=102 = 10256 、溝=102 = 10512 、
12
10
11
澗=102 = 101024 、正=102 = 102048 、 載=102 = 104096 、千万億兆京垓杼穣溝澗正載=108191 と、現
3 再掲:
無量大数の彼方へ http://www.sf.airnet.ne.jp/˜ts/language/largenumber.html
2.1. クラス 2 の巨大数
9
在の定義である無量大数とは比べ物にならないほどの大きな数になります。それでも、指数の部分が 100 万
に達していないので、まだクラス 2 です。
載よりも上の単位、極から上は、元の朱世傑による『算学啓蒙』において登場しました。ここで、極以
外の単位はすべて仏教から取られたものです。 恒河沙は「ガンジス川の砂」の意味 で、それだけ大きな数
ということです。阿僧祇は「数えることができない」、那由他は「極めて大きな数量」、不可思議「思い測っ
たり言葉で言い表したりすることができない」無量大数は、
『算学啓蒙』では「無量数」として登場し、
「量
ることのできない数」ということです。
この中で、恒河沙以外は「数え切れないほどの大きな数」と理解すれば良いのですが、恒河沙について
は、ガンジス川の砂の数という具体的な数になっているので、どの程度の大きさなのか見積もってみます。
今は、恒河沙と言えば日本では 1052 という意味になり、中国でも下数、中数、上数によって数は変わりま
す。仏教の中ではそういう数字を意味するものではなく、ガンジス川の砂の数という意味ですから、今の日
本で恒河沙を意味する 1052 と比較することは無意味です。
まずは、ガンジス川の大きさと砂粒の大きさを考える必要があります。Wikipedia によれば、全長は 2525km
とされています。川幅は数 km なので 4km 程度と考えて、面積を 10000km2 とします。深さをどこまで取
るのかは分かりませんが、仮に 1m の深さまで考えると、体積は 10km3 になります。問題は、砂の大きさで
す。砂は粒子の直径が 0.05-2mm のもので、それよりも小さい直径のものはシルトあるいは粘土と言われま
す。当時のインドにはそのような概念はなかったのでしょうから、全部ひっくるめて砂と呼ばれていたこと
でしょう。そうすると、現在では非常に小さくて粘土と呼ばれていたような粒子のものも、砂に含めて考え
るのかどうか、これによって値はだいぶ変わってきます。ここでは、暫定的に直径が 0.1mm であると考え
ます。次に、充填率を考える必要がありますが、充填率が低くて 50%であったとしても、充填率が 100%で
あると仮定して計算したときの 2 倍程度の誤差なので、これは許容誤差であると考えて充填率 100%でざっ
くりと計算すると、10km3 = 1010 m3 の中に 0.001mm3 = 10−12 m3 の粒子を隙間無く埋めた時の粒子の個
数なので、1022 となります。今の日本の数え方だと、100 垓程度であると見積もられます。
仏教では、とても長い時間を表すときに 劫（こう） という時間の単位が使われます。
「未来永劫」
「億劫」
「五劫のすり切れ」などの言葉は、ここから来ています。大谷大学の木村宣彰教授によれば4 、この「劫」
には、2 通りの意味があり、1 つ目は「磐石劫」で、四十里四方の大石を、いわゆる天人の羽衣で百年に一
度払い、その大きな石が摩滅して無くなってもなお「一劫」の時間は終わらないと譬えています。2 つ目は
「芥子劫」で、方四十里の城に小さな芥子粒を満たして百年に一度、一粒ずつ取り去り、その芥子がすべて
無くなってもなお尽きないほどの長い時間が一劫であるとのことです。
この時間がどの程度のものなのか「カガクの時間」というサイトでは、次のように計算しています。「磐
石劫」では5 、
「1 里=500m」
「原子=1 辺 0.2nm の立方体」
「1 回なでると、1 平方メートルの範囲の原子が
1 層はがれる」という仮定の元、4 杼 = 4 × 1024 年という計算結果を出しました。2 つ目の「芥子劫」につ
いては6 、「1 里=500m」、「けし粒=1 辺 0.5mm の立方体」、という仮定の元、6 杼 4000 垓 = 6.4 × 1024 年
という計算結果を出しました。磐石劫でも芥子劫でも同じ杼の単位になるのは面白いところです。宇宙の年
齢は 138 億年程度であるとされていますので7 、それと比べて 100 兆倍ほどの気の遠くなるほど長い時間で
す。恒河沙という数と劫という時間の単位を組み合わせれば、恒河沙劫というとても長い時間が表現出来ま
4 生活の中の仏教用語「劫」
（木村宣彰）
http://www.otani.ac.jp/yomu page/b yougo/nab3mq0000000r5r.html
http://d.hatena.ne.jp/inyoko/20111015/How long is kalpa2
6 けし粒はいつなくなる http://d.hatena.ne.jp/inyoko/20111008/How long is kalpa
7 Universe as an Infant: Fatter Than Expected and Kind of Lumpy (New York Times) http://nyti.ms/YrtRRV
5 天女が岩をなでたなら
第 2 章 原始帰納関数
10
すので、そういう表現があるか検索してみたところ、『首楞厳経』という経典に恒河沙劫という表現が出て
来て、親鸞が『尊号真像銘文』で引用していることが分かりました8 。恒河沙劫は、1022 × 1024 = 1046 年
=100 載年のオーダーになります。
2.1.3
グーゴル
次に、インド、中国由来の数以外の巨大数について見ます。
大きな数を表す言葉として、上記の億、兆…といった単位の他には、キロ (k, kilo-, 103 )、メガ (M, Mega-,
106 )、ギガ (G, Giga-109 )、テラ (T, Tera-1012 ) といった単位の頭につける接頭辞もあります。単位の頭に
これらの接頭辞をつけることで、キロメートル、キログラム、メガバイト、Mbps（メガビットパーセカン
ド）、メガピクセル、ギガバイト、テラバイトなどという単位ができます。なお、ハードディスク等の記憶
容量を表す時には、1 キロが 1000 ではなく 210 = 1024 を意味することがあるので、注意が必要です。こ
れは、コンピュータは 2 進数を基本としているので、1000 よりも 1024 の方が切りの良い数だからです。
1000 と 1024 は 2.4%の差なので誤差として考えられたためですが、近年は記憶容量が増加してテラバイ
ト (TB) というような大きさも使われていますので、10 進数との差は大きくなります。10 進数でテラは
1012 = 1, 000, 000, 000, 000 ですが、2 進数のテラは 240 = 1, 099, 511, 627, 776 なので、誤差は 10%ほどに
なります。その分容量が多いので得をしているわけですが、あえて 10 進数表記をすることで、容量を大き
く見せることもできます。さて、テラの上の接頭辞は、国際単位系の SI で、ペタ (P, Peta-1015 )、エクサ
(E, Exa-1018 )、ゼッタ (Z, Zetta-1021 )、 ヨッタ (Y, Yotta-1024 ) と定められています。現実に使う大きさ
としては、杼=1024 程度が上限であると考えられているということでしょう。
現実世界の現象をあらわす数字としては、どの程度の数字が最大となるのでしょうか。「天文学的数字」
という表現があるように、天文学では広大な宇宙のことを取り扱うため、非常に大きな数字が使われます。
「ガンジス川の砂の数」と言った時には、とても広いガンジス川にある、とても小さい砂粒の数なので、非
常に大きな数になりました。広い方の限界として宇宙の大きさ、小さい方の限界としては、素粒子の大き
さを考えることになるでしょう。その両方の限界を取ると、宇宙に存在する素粒子の数はいくつか？とい
う疑問になります。エディントンは、1938 年にケンブリッジ大学のトリニティ・カレッジでの講義 (Tarner
Lecture) で、宇宙に存在する全陽子の数が正確に 136 × 2256 個あり、全電子数も同じ数だけある、としまし
た。これが、 エディントン数 (Eddington number) 9 と呼ばれています。10 進数に直すと、1.574... × 1079
程度です。現在では、陽子の数はもっと多いとされています。陽子よりも小さい素粒子の単位で考えると、
その数は 1080 − 1085 程度であるとされています。現実には、10 進数で書いた時に 100 桁以上の数を扱うこ
とはなさそうです。
英語での大きな数の表記には、混乱があります。million は 100 万を意味しますが、その上の billion は 10
億をあらわす場合と 1 兆をあらわす場合があります。現在は、billion が 10 億をあらわす short scale が主流
になっています。Billion が 1 兆をあらわす long scale は、かつてイギリスで使われていましたが、現在はイ
ギリスでも short scale が基本です。ただし、英語が母国語ではないヨーロッパ大陸や南米では、long scale
が使われているところもあります。Short scale と long scale の関係は、ちょうど万進と万万進の関係のよ
うなもので、short scale が千進、long scale が千千進と言えば分かりやすいと思います。つまり、million
8 WikiArc:
ノート:首楞厳経 http://bit.ly/1b4Myz9 (labo.wikidharma.org)
- Eddington Number http://mathworld.wolfram.com/EddingtonNumber.html
9 MathWorld
2.1. クラス 2 の巨大数
11
から先、billion, trillion, quadrillion, … と進んで行くごとに、short scale では千倍、long scale では千千
倍、つまり 100 万倍になります。数の一覧は Wikipedia の Names of large numbers
63
10
にまとめられてい
120
ます。その表では、vigintillion=10
(long scale では 10 ) までは千倍ずつ一通りの単位が書かれていて、
次にいきなり センティリオン (centillion) = 10303 (long scale では 10600 ) になっています。また、それと
は別に グーゴル googol=10100 と googolplex=1010
100
が書かれています。Googolplex はクラス 2 ではない
ので、クラス 2 の中では最大は centillion です。Google の名前は、googol から来ているようです。
【定義】グーゴル
グーゴル = 10100
Large Numbers のムナフォ氏は、6 才の時には知っていた最大の数が million(100 万) で、7 才の時に母
親にその上の単位を聞いて、billion(10 億) と trillion(兆) の単位を知り、さらに 8 才の時に学校の図書館で
読んだ本で vigintillion(1063 ) という数を覚えて嬉しくなり、校庭の砂に
1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
と書いて、いじめられたという過去があるようです。
また、vigintillion の先を、規則的に 1000 倍ずつ名前を定義する方法が提案されていて、その表では、最
大は ミリニリオン (millinillion) = 103003 となっています。
日常生活で使うのは、クラス 2 の中でも非常に小さい数までですので、数に名前がつけられるのも、た
いていはここまでです。
それでは、数学の世界ではどうでしょうか。数学の世界では、現実の世界と関連づけずに数字の性質を
考えますので、日常生活で取り扱う範囲の数を超えた大きな数を取り扱うことがあります。たとえば、素数
は 1 とそれ自身以外に約数を持たない数で、2,3,5,7,11,…と続きますが、無限にどこまでも続きます。素数
が無限である事を証明するのは簡単で、もし素数が有限だったと仮定すると、その素数全てをかけて 1 を
足した数は、どの数でも割り切れなくて素数になってしまいますから、そのようなことはありえません。し
たがって、素数は無限にあります。このように、「最大の素数」は存在しないので、巨大数候補から外れま
す。2013 年 1 月 25 日に、その時点で最大の素数 257885161 − 1 が見つかりました。これはメルセンヌ素数
です。クラス 3 の数になります。
2011 年 12 月に、その時点で最大の双子素数 3756801695685 × 2666669 ± 1 ≈ 8.73 × 10200699 が見つかり
ました。これは、クラス 2 の巨大数です。双子素数とは、(3,5), (5,7), (11,13) のように、差が 2 である 2 つ
の素数の組です。双子素数が無限に存在するかどうかはまだ分かっていないので「最大の双子素数」が巨大
数となるかどうかは分かりません。
それではここで、表 2.1 にクラス 2 の巨大数を、小さいものから大きいものへと順番にまとめます。
2.1.4
数の比較
それでは次に、このような巨大数の大きさをどのように比較するのかを考えましょう。
10 Wikipedia:
Names of large numbers https://en.wikipedia.org/wiki/Names of large numbers
第 2 章 原始帰納関数
12
名称
表 2.1: クラス 2 の巨大数（下の数ほど大きい）
値
恒河沙劫の年数の見積もり
1046
無量大数
1068
136 × 2256 ≈ 1.57 × 1079
10100
エディントン数 (Eddington number)
グーゴル (googol)
センティリオン (centillion)
ミリニリオン (millinillion)
上数の載
クラス 2 の数の上限
10303
103003
104096
6
101000000 = 1010
クラス 2 までの数は、数の大小比較が簡単にできます。10 進数で書かれていれば、まずは桁数を比較し
て、桁数が同じであれば一番上の桁から順番に大きさを比較すれば良いのです。数が 3.23 × 1021 のような
指数表記で書かれていれば、桁数を数える必要もないので楽です。ただし、10 進数表記あるいは 10 進数
の指数表記同士で書かれていない数を比較する時には、計算をする必要が出てきます。計算は、手計算で
もできますが、電卓を使えばできます。電卓には、スマホのアプリやパソコンのソフト等、色々あります。
Google の検索窓に計算式を打ち込めば、計算が出来ます。性能によって、表示出来る最大の数（指数表示
の時の最大の指数）、表示される桁数、内部で計算されている桁数、等が変わります。
カシオが運営している高精度計算サイト11 は、強力です。「生活の計算」「数学・物理」「専門的な計算」
それぞれ様々な実用的な計算をすることができて、実用的にも便利ですし、なんといっても「フリー計算」
の機能が高いので、本書のような趣味の計算をするときにも便利に使えます。様々な関数が扱え、桁数は
50 桁までの精度が得られ、さらに精度保証の機能がついています。コンピュータで計算をする時には、計
算機の内部で保持している変数の桁数に限界があるため、限界以上の桁は丸めて計算をするため、計算結
果に誤差が出ます。そこで、計算結果を丸める時に、必ず「最小の値」と「最大の値」を同時に計算するこ
とで（ざっくりと言えば、ということです。しっかりと勉強したい方は大石進一氏のサイト12 を参照して
下さい。）、最大でどの程度の誤差が生じるかを見積もることができます。この高精度計算サイトでエディ
ントン数を 50 桁まで計算すると、1.5747724136275002577605653961181555468044717914527 × 1079 と計
算できます。しかし、エディントン数は 80 桁あるので、最後の 30 桁が計算できていません。そこで、桁
数に制限のない任意精度計算機 (Arbitrary Precision Calculator)
13 14
を使えば、エディントン数を正確に
計算できます。計算結果は、
15747724136275002577605653961181555468044717914527116709366231425076185631031296
となります。このような計算機を使えば、クラス 2 の数はだいたい大小比較ができます。
手元の電卓ではエラーが出てしまうような大きな数を計算する時には、対数 (log) を使うと、大きさを知
る事ができます。対数には、底を 10 とする常用対数と、底を e とする自然対数があるので、常用対数で計
算した時にはその数 a に対する 10a を、自然対数で計算した時には exp(a) = ea を計算することになりま
11 高精度計算サイト
(CASIO) http://keisan.casio.jp/
http://www.oishi.info.waseda.ac.jp/˜oishi/FAQ/FAQ.html
13 Arbitrary Precision Calculator http://apfloat.appspot.com/
14 Big Integer Calculator http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm
12 精度保証付き数値計算
2.2. クラス 3 の巨大数 - 不可説不可説転とグーゴルプレックス
13
す。ここでは、常用対数を使います。双子素数 3756801695685 × 2666669 ± 1 の常用対数の大きさを
log(3756801695685 × 2666669 ± 1) ≈
≈
log(3756801695685) + 666669 × log(2)
200699.94099758
とまず計算してから、双子素数のおおよその大きさを
10200699.94099758
= 100.94099758+200699
= 100.94099758 × 10200699
≈ 8.729665 × 10200699
と計算すれば良いのです。指数が 100 万までのクラス 2 の数であれば、対数を取れば 100 万までの数にな
りますので、どんな電卓でも簡単に計算出来ます。ただし、対数が計算出来ない電卓の場合には、しかたあ
りません。
2.2
クラス 3 の巨大数 - 不可説不可説転とグーゴルプレックス
6
クラス 3 の数 (1010 − 1010
106
) : クラス 2 を超えると、10 進数で数字を書いて大きさを比較するのが無
6
理になります。ここでも、クラス 2 までと同様、クラス 2 の上限である 1010 を 10 の指数に持ってきて、
106
1010
をクラス 3 の上限とします。ここで、クラスの定義をフォーマルな形で記しておきます。
【定義】自然数のクラス
数列 c(n) を c(0) = 6, c(n + 1) = 10c(n) で定義する。
クラス n の自然数とは、
(i) n=0 の時は、c(0) 以下の自然数である。
(ii) n > 0 の時は、c(n-1) よりも大きく、c(n) 以下の自然数である。
ここでまた、仏教で使われている数の大きさについての話になります。インドの数の単位では、本来は下
数の単位が使われていましたが、後の仏典では上数として使われることがあり、華厳経第 45 巻、阿僧祇品
第三十には、「100 洛叉（らくしゃ=10 万）を 1 倶胝（くてい）とする。倶胝倶胝を 1 阿ゆ多（あゆた）と
する。阿ゆ多阿ゆ多を 1 那由他（なゆた）とする。那由他那由他を 1 頻波羅（びんばら） とする。（中略）
不可説転不可説転を 1 不可説不可説とする。このまた不可説不可説（倍）を 1 不可説不可説転（ふかせつ
ふかせつてん）とする。」と書かれています。「倶胝倶胝を 1 阿ゆ多とす」とは、倶胝×倶胝=阿ゆ多とい
うことなので、107 を意味する倶胝以上は、中国の上数と同じように 2 乗すると次の単位になっています。
したがって、倶胝（くてい）=107 、阿ゆ多（あゆた）=107×2 = 1028 、那由他（なゆた）=107
× 2
2
= 1056 、
頻波羅（びんばら）=107 2 = 10112 と、2 乗することで指数が 2 倍になり、指数の中の 2 の指数が 1 増え
× n
ます。つまり、倶胝の n 個上の単位は 107 2 となります。 不可説不可説転（ふかせつふかせつてん） は、
× 3
倶胝の 122 個上の単位なので、107×2
不可説不可説転 = 107×2
122
になります。
【定義】不可説不可説転
122
第 2 章 原始帰納関数
14
グーゴルプレックス (googolplex) は数の単位で、10 のグーゴル乗 (10googol )、つまり 1010
100
です。
【定義】グーゴルプレックス
グーゴルプレックス = 1010
100
クラス 3 の数字は、通常の計算で比較するのが無理です。不可説不可説転まで大きくなると、指数表記を
した時に指数の部分が 7 × 2122 という大きな数になりますので、通常の電卓では計算範囲を超えます。た
とえば、前節で紹介した高精度計算サイトを使って計算しても、計算結果は∞と表示されるだけで、計算の
上限を超えてしまっています。
このような大きさの数を比較する時には、対数を使うよりありません。不可説不可説転とグーゴルプレッ
クスの比較であれば、すでに両者とも 10x の形になっているので、簡単に比較できます。両者の対数を取っ
た、7 × 2122 と 10100 を比較すれば良いのです。
7 × 2122 = 37218383881977644441306597687849648128 ≈ 3.72 × 1037
と計算されるので、これよりも 10100 の方が大きく、グーゴルプレックスは不可説不可説転よりも大きいこ
とが分かります。
クラス 4 の巨大数 - 第 2 スキューズ数
2.3
106
6
1010
6
1010
− 1010
) : クラスの定義より、クラス 4 の上限は 1010
です。このクラス
になると、指数表記で書く事は無理で、大小を比較するには、対数を 2∼3 回取る必要があります。
クラス 4 の数 (1010
それでは、次の巨大数の話をするために、少し準備をします。素数計数関数 (Prime counting function)
π(x)
15
は、x 以下の素数の個数を返す関数です。対数積分 li(x)
Z x
dt
li(x) =
0 ln(t)
16
は、全ての正の実数 x 6= 1 において、
(2.1)
で定義される関数です。素数定理によれば、π(x) は漸近的に li(x) に等しくなりますが、計算がなされて
いる範囲では、常に π(x) < li(x) となっていて、今でも π(x) > li(x) となるような具体的な x は見つかっ
ていません。ところが、π(x) と li(x) は無限回大小関係が逆転することが証明されているため、いつはじめ
て π(x) > li(x) となる x が出てくるのかが研究されてきました。
17 18
スキューズ数 (Skewes Number)
ee
予想が正しいとした時に、Sk1 = e
79
には 2 つあります。スキューズは、1933 年の論文で、リーマン
以下の数に π(x) > li(x) となる数が存在することを証明しました。
この Sk1 が 第 1 スキューズ数 と呼ばれます。さらにスキューズは、1995 年に、リーマン予想を仮定する
ことなしに、 第 2 スキューズ数 Sk2 = ee
7.705
ee
以下の数で π(x) > li(x) となる x が存在することを証明
しました。この上限は、Bays and Hudson (2000)
19
によって約 1.3983 × 10316 にまで下げられています。
スキューズ数はいずれもクラス 4 の数です。Sk1 は 1010
かりやすく 1010
15 MathWorld
3
1010
1034
程度です。Sk2 は 1010
10963
程度ですが、分
とされることもあります。
- Prime Counting Function http://mathworld.wolfram.com/PrimeCountingFunction.html
- Logarithmic Integral http://mathworld.wolfram.com/LogarithmicIntegral.html
17 Wikipedia: スキューズ数 http://bit.ly/19xZhqQ (ja.wikipedia.org)
18 MathWorld - Skewes Number http://mathworld.wolfram.com/SkewesNumber.html
19 Bays and Hudson (2000), ”A new bound for the smallest x with π(x) > li(x) ”, Mathematics of Computation 69 (231):
1285-1296. http://bit.ly/16EtsQx (www.ams.org)
16 MathWorld
2.4. クラス 5 以上の巨大数
15
【定義】第 2 スキューズ数
第 2 スキューズ数 = ee
7.705
ee
≈ 1010
3
1010
ムナフォ氏は、通常の計算プログラムでは大きすぎて計算できない（オーバーフローしてしまう）よう
な巨大数を計算するためのプログラム ハイパーカルク (Hypercalc)
20
を作成しました。Hypercalc を使
うと、第 2 スキューズ数は
入力: e^e^e^e^7.705
結果: 10 ^ [ 10 ^ ( 3.299943221955 x 10 ^ 963 ) ]
と、計算ができます。第 2 スキューズ数をこのように直接計算できるプログラムは、他にはなかなかない
だろうと思います。
2.4
クラス 5 以上の巨大数
宇宙論で使われた最大の巨大数（であると思われる数）に、クラス５の巨大数である
宇宙論で使われた最大の数
10^10^10^10^10^1.1
という数字があります21 。これは、Page (1994) 22 が「リンデの確率過程的インフレーションという説で
生まれるかもしれないあらゆる多重宇宙の全質量を 1 個のブラックホールに潰して適当な箱の中に入れた」
と仮定したときにブラックホールの蒸発後にまたブラックホールができるまで23 のポアンカレ再帰時間24
を計算したものです。この数字は現在の状態の宇宙に対するポアンカレ再帰時間ではないので、「宇宙の全
ての物質が元に戻る」25 という説明は不正確です。意味のある数字というよりは、どちらかというと、巨
大数を作ることを目的に計算された数字、ということのようです。単位はプランク時間 (5.391 × 10−44 秒)
でも 1000 年でもなんでもいい、と Page (1994) に書かれているように、クラス 5 の数字になると、クラス
4 までの数字をかけても割っても右肩の数字（この場合だと 1.1）にほとんど影響を与えなくなってしまう
ため、時間の単位を気にする必要すらなくなってしまいます。このことは、次節以降で色々と計算をしてい
きます。
クラスが 1 つ上がるごとに、前のクラスとは比べものにならないほどに大きな巨大数の世界が広がって
います。ただし、クラス 5 以上になると、具体的に名前がつけられている数はあまりありません。クラス
7625597484986（クラス 7 兆以上）の巨大数「トリトリ」については、次の節で説明します。クラス 5 より
も大きな巨大数は、ほとんどがクラスという概念ではとても表し切れないような、別次元の巨大数になり
ます。それらについては、本書でこれから少しずつ見て行きます。
20 Hypercalc
- The Calculator That Doesn’t Overflow http://www.mrob.com/pub/perl/hypercalc.html
Possible Time - Numberphile http://www.numberphile.com/videos/longest time.html
22 Page (1994) ”Information loss in black holes and/or conscious beings?” http://arxiv.org/pdf/hep-th/9411193
23 宇宙物理たん bot による説明 https://twitter.com/astrophys tan/status/391928927012134912
24 Wikipedia - Poincar´
e recurrence theorem http://en.wikipedia.org/wiki/Poincar´
e recurrence theorem
25 ニコニコ動画: 時間の比較 http://www.nicovideo.jp/watch/nm16202721
21 Longest
第 2 章 原始帰納関数
16
2.5
矢印表記とハイパー演算子 - トリトリ
ここまでは、クラスが上がると気の遠くなるような大きさの数字となることを見てきましたが、ここか
らは、クラスという概念を使っても間に合わないほどの大きな数を表記する方法について見て行きます。
クヌースの矢印表記 (arrow notation)
26 27
は、以下で定義されます。
【定義】クヌースの矢印表記
x↑y
= xy
x ↑↑ 2
=
x ↑ x, x ↑↑ y = x ↑ (x ↑↑ (y − 1))
x ↑↑↑ 2
=
x ↑↑ x, x ↑↑↑ y = x ↑↑ (x ↑↑↑ (y − 1))
x ↑↑↑↑ 2
=
x ↑↑↑ x, x ↑↑↑↑ y = x ↑↑↑ (x ↑↑↑↑ (y − 1))
n
x↑ y
= x(n 個の↑)y
具体的に計算をしてみましょう。まずは、↑が 1 つの場合です。これは、指数と同じです。↑を連結させ
ると、指数と同じように右から順番に計算します。Hypercalc
3↑3
3↑3↑3
=
28
を使うと、次の様に計算されます。
33 = 27
3
= 33 = 327 = 7625597484987
33
= 1.35 × 10 ↑ 3638334640024
3↑3↑3↑3
=
33
3↑3↑3↑3↑3
=
10 ↑ (6.46 × 10 ↑ 3638334640023)
3↑3↑3↑3↑3↑3
=
10 ↑ 10 ↑ (6.46 × 10 ↑ 3638334640023)
3↑3↑3↑3↑3↑3↑3
=
10 ↑ 10 ↑ 10 ↑ (6.46 × 10 ↑ 3638334640023)
3↑3↑3↑3↑3↑3↑3↑3
= 10 ↑ 10 ↑ 10 ↑ 10 ↑ (6.46 × 10 ↑ 3638334640023)
ここで、Hypercalc では、10 ↑ 10 ↑ 10 ↑ 10 ↑ (6.46 × 10 ↑ 3638334640023) という計算結果は、
「4 PT
( 6.46 × 10 ˆ 3638334640023 )」と表示されます。最初の 10 ↑を 4 回繰り返す部分を 4 PT と表示するこ
とで、オーバーフローしないようにしています。
さて、ここで右辺を見ると、最後のかっこの中が、途中からずっと同じ数 6.46 × 10 ↑ 3638334640023 =
10 ↑ 10 ↑ 12.56 になっています。つまり、3 ↑を 1 つつけることと、10 ↑をつけることが、途中からまっ
たく変わらなくなってしまっています。本当は変わるのですが、有効桁数内では変わらない、ということで
す。ここで、上のピラミッドを見やすく書き直します。
3↑3
=
3↑3↑3 =
3↑3↑3↑3
3↑3↑3↑3↑3
26 巨大数資料
27
10 ↑ 12.88
= 10 ↑ 10 ↑ 12.56
= 10 ↑ 10 ↑ 10 ↑ 12.56
wiki - タワー表記 http://www51.atwiki.jp/largenumbers/pages/7.html
MathWorld - Arrow Notation http://mathworld.wolfram.com/ArrowNotation.html
28 再掲: Hypercalc - The Calculator That Doesn’t Overflow http://www.mrob.com/pub/perl/hypercalc.html
27 Wolfram
2.5. 矢印表記とハイパー演算子 - トリトリ
3↑3↑3↑3↑3↑3
17
=
3↑3↑3↑3↑3↑3↑3 =
3↑3↑3↑3↑3↑3↑3↑3 =
10 ↑ 10 ↑ 10 ↑ 10 ↑ 12.56
10 ↑ 10 ↑ 10 ↑ 10 ↑ 10 ↑ 12.56
10 ↑ 10 ↑ 10 ↑ 10 ↑ 10 ↑ 10 ↑ 12.56
左では 3 ↑を増やして、右では 10 ↑を増やしています。一番右の数は、27,12.88,12.56、と小さくなり、そ
れ以上は小さくなりません。一番右の数を少しだけ増やす効果は、このピラミッドで下に行けばいくほど爆
発的に大きくなります。それに対して、3 ↑を 10 ↑に変える効果というのはたいした効果がないので、ほ
とんど無視できてしまいます。
したがって、巨大数を作るにあたって、タワーの最初の数字は 10 ではなくて 3 で十分だ、ということに
なります。この段階では 2 でもいいのですが、2 にしてしまうと、この先の計算で 2 ↑↑↑↑ 2=2 ↑↑↑
2=2 ↑↑ 2=2 ↑ 2=4 となって面白くないので、3 を使っています。
そのようなわけで、3 ↑ 3 ↑ 3 はクラス 2 の数ですが、3 ↑ 3 ↑ 3 ↑ 3 はクラス 3、3 ↑ 3 ↑ 3 ↑ 3 ↑ 3 は
クラス 4、と 1 つ↑が増えるごとにクラスが 1 つ上がります。3 ↑ 3 ↑ 3 ↑ 3 ↑ 3 ↑ 3 はクラス 5 なので、
第 2 スキューズ数を超えます。
なぜ、ベースを 3 にしても 10 にしても、増え方が変わらないのでしょうか。ある数 x に対して、3x と
10x でどれだけの違いがあるかを考えると、
10x = (3log3 (10) )x = 3xlog3 (10) ≈ 32.1x
x
x
なので、x が 2.1 倍程度増える効果になります。次に、1010 と 33 でどの程度の違いになるかというと、
x
log3 (1010 ) ≈ 2.1 × 10x ≈ 2.1 × 32.1x
1010
x
≈ 32.1×3
2.1x
= 33
2.1x+log3 (2.1)
≈ 33
2.1x+0.68
となり、x を 2.1 倍して 0.68 を足す効果になります。一番下の数字を 3 から 10 に増やす効果は、1 つ目の
冪乗箇所を 2.1 倍する程度の効果、2 つ目の冪乗箇所に 0.68 を足す効果となり、3 つ目の冪乗箇所に至って
は極めて小さな効果になります。たとえば、上で計算された
3 ↑ 3 ↑ 3 ↑ 3 ↑ 3 ↑ 3 = 10 ↑ 10 ↑ 10 ↑ 10 ↑ 12.56
という式において、x=12.56 とすれば 2.1x+0.68=27.056 で、ほぼ 3 ↑ 3=27 と等しくなっているので、
2.1x+0.68 程度の効果がある、という見積もりが正しいことが分かります。
Hypercalc で、x=10 ↑ 10 ↑ 10 ↑ 10 としたときの 2x と xx を計算したところ、同じ 10 ↑ 10 ↑ 10 ↑
10 ↑ 10 になりました。つまり、2x ≈ xx と考えて良いことになります。ここで、≈ の記号は、数字の大き
さそのものは非常に差が大きいけれど、対数を 4 回取って比較すると差が計算出来ない程に小さくなるの
で、同じ程度の数だと考えて良い、という意味です。つまり、
log(log(log(log(2x )))) ≈ log(log(log(log(xx )))) ≈ 10
ということを、2x ≈ xx と書きました。巨大数は正確な計算ができないので、このような近似の取り扱いが
必要になります。
次は、↑が 2 つ並んだ場合です。これを特別に パワータワー (power tower)
29 Wolfram
MathWorld - Power Tower http://mathworld.wolfram.com/PowerTower.html
29
とも言います。
第 2 章 原始帰納関数
18
x ↑↑ y = x ↑ (x ↑↑ (y - 1)) = x ↑ (x ↑ (x ↑↑ (y - 2))) = … = x ↑ x ↑…↑ x (x が y 個)
となり、指数（パワー）がタワーのように連なるのでパワータワーと言います。
また、これを テトレーション (tetration)
31
ンは、グッドスタイン
30
あるいは 超冪（ちょうべき） とも言います。テトレーショ
がギリシャ語の接頭辞で 4 を意味する tetra-から作った言葉です。繰り返しで得
られる 4 番目の演算子なので、 ハイパー 4 演算子（hyper-4） とも言います。 ハイパー n 演算子 Hn (a, b)
は、以下で定義されます32 。
【定義】ハイパー n 演算子 Hn (a, b)


b+1





 a
Hn (a, b) =
0


 1




Hn−1 (a, Hn (a, b − 1))
(n = 0)
(n = 1, b = 0)
(n = 2, b = 0)
(2.2)
(n ≥ 3, b = 0)
(それ以外)
H0 (a, b) = b + 1 は、後者
H1 (a, b) = a + b は、加算（後者の繰り返し）
H2 (a, b) = a × b は、乗算（加算の繰り返し）
H3 (a, b) = ab は、冪乗（乗算の繰り返し）
H4 (a, b) = a ↑↑ b は、超冪（冪乗の繰り返し）またはテトレーション
H5 (a, b) = a ↑↑↑ b は、ペンテーション（テトレーションの繰り返し）
H6 (a, b) = a ↑4 b は、ヘキセーション（ペンテーションの繰り返し）
Hn (a, b) = a ↑n−2 b(n ≥ 3)
それでは、テトレーション↑↑を連ねていきます。
3 ↑↑ 3 =
3 ↑↑ 3 ↑↑ 3 =
3 ↑ 3 ↑ 3 = 7625597484987
3 ↑↑ 7625597484987 = 3 ↑ 3 ↑…↑ 3(3 が 7625597484987 個
ということで、この時点でクラス 7625597484986 の巨大な数になります。Hypercalc で計算しようにも、
「3ˆ」を 7 兆個以上打ち込まないとなりませんので、無理です。仮に打ち込んだとしたら、
「7625597484983
PT ( 6.46 × 10 ˆ 3638334640023 )」という結果が表示されることでしょう。
3 ↑↑ 3 ↑↑ 3 ↑↑ 3 = 3 ↑ 3 ↑…↑ 3 (3 が 3 ↑↑ 3 ↑↑ 3 個)
となると、クラス 3 ↑↑ 3 ↑↑ 3 程度の巨大数です。Hypercalc では計算できません。まず、3 を 3 ↑
↑ 3 ↑↑ 3 回入力することが不可能ですし、仮に入力できて、計算の時間とメモリの制約を無視しても、
Hypercalc の計算できる最大値は 10 ↑↑ (1010 ) であるとされていて、10 ↑↑ (3 ↑↑ 3 ↑↑ 3) 程度のこの
数はオーバーフローです。Hypercalc ですらオーバーフローしてしまう巨大数となりました。
そこで、クラスの概念を拡張して ハイパークラス を定義します。これは、本書独自の定義です。
30 Wikipedia
- テトレーション http://bit.ly/16PxCYh (ja.wikipedia.org)
L. Goodstein (1947). ”Transfinite Ordinals in Recursive Number Theory”. Journal of Symbolic Logic 12(4): 123-129.
http://dx.doi.org/10.2307/2266486
32 Wikipedia - ハイパー演算子 http://bit.ly/19zpxBg (ja.wikipedia.org)
31 R.
2.5. 矢印表記とハイパー演算子 - トリトリ
19
【定義】自然数のハイパークラス
数列 hc(n) を hc(0) = 6, hc(n + 1) = c(hc(n)) で定義する。ここで、c(n) についてはクラスの定義
(p.12 の第 2.2 節) 参照。
ハイパークラス n の自然数とは、
(i) n=0 の時は、hc(0) 以下の自然数である。
(ii) n > 0 の時は、hc(n − 1) よりも大きく、hc(n) 以下の自然数である。
この定義は、クラスの定義とほとんど同じで、変わっているところは、hc(n + 1) = c(hc(n)) の箇所です。
クラスの定義では、c(n + 1) = 10c(n) となっていました。クラスを上げるための演算は 10 ↑ x ですが、ハ
イパークラスを上げるための演算は c(x) を使っています。
ハイパークラス 1 は、クラス 6 までの数です。したがって、前節で示したクラス 4 までの巨大数は、す
べてハイパークラス 1 になります。ハイパークラス 2 は、N をハイパークラス 1 の上限であるとしたとき
に、クラス N までの数です。同様に、ハイパークラス 3 は、クラス（ハイパークラス 2 の数）で表される
自然数です。
このように定義すると、3 ↑↑ 3 はハイパークラス 1、3 ↑↑ 3 ↑↑ 3 はハイパークラス 2、3 ↑↑ 3 ↑↑
3 ↑↑ 3 はハイパークラス 3、というように、テトレーションを繰り返すごとにハイパークラスが 1 つ増加
します。ハイパークラス 3 以上の数は、Hypercalc を使っても計算出来ません。
タワーが 3 つ並ぶと、超冪を繰り返す ハイパー 5 演算子 で、 ペンテーション (pentation)
外の巨大数マニア、 グーゴロジスト
34
33
達は、3 に 3 をペンテーションした数を トリトリ (tritri)
です。海
35
と名
付けています。これからも出て来る数で、原始帰納でできる巨大数の例としては面白いので、定義を書いて
おきます。
【定義】トリトリ
トリトリ = 3 ↑↑↑ 3 = 3 ↑↑ 3 ↑↑ 3
トリトリは、クラス 7625597484986、ハイパークラス 2 の巨大数である。
また、10 ↑↑↑ 100 は gaggol と呼ぶそうです。これは、ハイパークラス 100 の巨大数です。
タワーが 4 つ並ぶと、ハイパー 5 を繰り返す ハイパー 6 演算子 で、 ヘキセーション (hexation) になり
ます。
3 ↑↑↑↑ 3 = 3 ↑↑↑ 3 ↑↑↑ 3 = 3 ↑↑↑トリトリ = 3 ↑↑ 3 ↑↑…↑↑ 3 (3 がトリトリ個）
となります。テトレーションの計算をトリトリ回繰り替えした数が 3 ↑↑↑↑ 3 なので、ハイパークラ
ストリトリほどの大きさの数ということになります。なんだか分からないけどとにかく大きな数、というよ
り他にないような大きな数です。これが、後のグラハム数の定義で出て来る f(4) で、グラハム数はこの数
がスタートになっています。
このように、↑という記号を導入したことで、四則演算やべき乗などの記号だけでは、とても書ききれ
ない、Hypercalc をもってしても太刀打ちできないほどの想像を絶する大きな数を表現することができまし
33 Googology
Wiki - Pentation http://googology.wikia.com/wiki/Pentation
Wiki - Googology http://googology.wikia.com/wiki/Googology
35 Googology Wiki - Tritri http://googology.wikia.com/wiki/Tritri
34 Googology
第 2 章 原始帰納関数
20
た。スキューズ数などのこれまで見たような巨大数は、トリトリから見ると、小さすぎて話にならない数、
と言うことができます。
さて、このような巨大数の大きさは、どのように評価すれば良いのでしょうか。そもそも正確な計算が
現実的な時間ではできない数なので、やみくもに計算を繰り返しても何も分かりません。大切なことは、ど
のような計算をしているか、という構造を見ること、関数の性質をよく知ることです。矢印表記の性質と
して、
1. 同じ形の表記であれば、左の数字を大きくするよりも、右の数字を大きくする効果の方が大きい。
2. 数字を大きくする効果よりも、繰り返し数を増やす効果の方が大きい。
3. 繰り替えし数を増やす効果よりも、↑の数を増やす効果の方が大きい。
たとえば、以下のような関係は分かります。
100 ↑↑↑ 100
< 3 ↑↑↑ 101
100000 ↑↑↑ 100000 ↑↑↑ 100000 < 3 ↑↑↑ 3 ↑↑↑ 3 ↑↑↑ 3
3 ↑100 3 ↑100 3 ↑100 3 ↑100 3
=
3 ↑101 5 < 3 ↑102 3
つまり、巨大数を作るという観点からは、使われる数字を大きくしても、繰り返しの数を増やしても、↑
の数を増やす効果にはかなわないません。↑の数を増やすことが最も効率的である、ということになりま
す。色々な数字と↑が入り乱れているタワー表記の数があったときには、一番↑の数が大きい場所の↑の本
数を x として、3 ↑x+2 3 という数を作れば、その数の方が大きい、ということになります。
さて、ここから先は Hypercalc で計算できないような大きな数の話になりますが、もう少し Hypercalc
で遊んでみます。Hypercalc で計算できる演算は、四則演算、冪乗、階乗です。そこで、階乗を繰り返したら
どうなるかを計算してみましょう。ここで、階乗を繰り返した!!!という記号は、通常は 10!!! = 10 × 7 × 4 × 1
のように定義されていますが、Hypercalc では 10!!! = ((10!)!)! として計算します。したがって、!を連続し
て打ち込めば、階乗の繰り返しを簡単に計算できます。ここでは、3!n = (…(((3!)!)!)…) と、!を n 回繰り返
す演算を !n と表記します。また、n PT は 10 ↑ の n 回の繰り返しを表します。
3!
=
6 (クラス 0)
3!2 = (3!)!
=
720 (クラス 1)
3
3! = ((3!)!)!
= 2 P T 3.242147497 (クラス 2)
3!4
= 3 P T 3.242952972 (クラス 3)
5
3!
= 4 P T 3.242952972 (クラス 4)
3!6
= 5 P T 3.242952972 (クラス 5)
100
= 99 P T 3.242952972 (クラス 99)
3!
階乗は掛け算の繰り返しなので、冪乗程度の増加率です。それを繰り返すことで、クラスが 1 つずつ上が
り、3.242952972 の部分は動かなくなります。クラス n の巨大数に階乗をすると、クラス n+1 の巨大数に
なる、ということになりそうです。
2.6. グッドスタイン数列
2.6
21
グッドスタイン数列
グッドスタイン数列 (Goodstein Sequence)
36 37 38
は、面白い性質を持った数列です。グッドスタイン
数列を定義するためには、まず n を底とした遺伝的記法 (Hereditary base-n notation) について定義する
必要があります。
自然数の n 進数表記は、
k
X
ai ni = ak nk + ak−1 nk−1 + · · · + a0 n0
i=0
と書く事ができます。たとえば、1234 の 10 進数表記は
1234 = 1 × 103 + 2 × 102 + 3 × 101 + 4
です。ここで、ak nk は nk + nk + · · · + nk なので、nk の和で書くこともできます。たとえば、
1234 = 103 + 102 + 102 + 101 + 101 + 101 + 100 + 100 + 100 + 100
です。日本語版 Wikipedia では、この記法を取っていますが、Mathworld と英語版 Wikipedia では、この
記法を取らず ak nk を採用しているので、ak nk のまま話を進めます。さて、ak nk の和で表した時に、指数
の部分をさらに n 進数に分解します。そこでまた出て来た指数の部分を、さらに n 進数に分解します。こ
のようにすると、出て来る数が全て n 以下の数となるように、記述出来ます。これが遺伝的記法です。
1234 で 10 進数の場合は、すでに出て来る数がすべて 9 以下となっているので、上記のままで遺伝的記法
になります。これを、3 を底にする遺伝的記法に直します。
36 + 2 × 35 + 2 × 32 + 1
1234 =
= 32×3 + 2 × 33+2 + 2 × 32 + 1
このように、出てくる数がすべて 3 以下になります。続いて、2 を底にする遺伝的記法にします。
1234 =
210 + 27 + 26 + 24 + 2
= 22
3
= 22
2+1
+2
+ 22
+2
2
+2+1
+ 22
2
+ 22
+2+1
2
+2
+ 22
2
2
+ 22 + 2
+2
2
+ 22 + 2
これが、遺伝的記法です。続いて、グッドスタイン数列の定義を記します。
【定義】グッドスタイン数列
自然数 n の b を底とする遺伝的記法を書き、b を b+1 に書き換えることで得られる数字を B[b](n) と
する。
このとき、G0 (n) = n からはじまるグッドスタイン数列を Gk (n) = B[k + 1](Gk−1 (n)) − 1 で定義
する。結果が 0 となったときに数列は終了する。
36 Wikipedia:
-グッドスタインの定理 http://bit.ly/1bFM4nk (ja.wikipedia.org)
37 Wolfram MathWorld - Goodstein Sequence http://mathworld.wolfram.com/GoodsteinSequence.html
38 Googology WIki - Goodstein sequence http://googology.wikia.com/wiki/Goodstein sequence
第 2 章 原始帰納関数
22
3 から始まるグッドスタイン数列39 の計算をすると、
G0 (3) =
3=2+1
G1 (3) =
B[2](G0 (3)) − 1 = B[2](3) − 1 = 3 + 1 − 1 = 3
G2 (3) =
B[3](G1 (3)) − 1 = B[3](3) − 1 = 4 − 1 = 3
G3 (3) =
B[4](G2 (3)) − 1 = B[4](3) − 1 = 3 − 1 = 2
G4 (3) =
B[5](G3 (3)) − 1 = B[5](2) − 1 = 2 − 1 = 1
G5 (3) =
B[5](G4 (3)) − 1 = B[6](1) − 1 = 1 − 1 = 0
と計算出来ます。まず、最初に G0 (3) を 2 を底とする遺伝的記法で「2+1」と書きます。次に、G1 (3) の計
算では、G0 (3) = 3 に対して、B[2] の操作、つまり 2 を底とする遺伝的記法で、2 を 3 に書き換える操作を
します。つまり、
「2+1」の 2 の部分を 3 に書き換えて、
「3+1」とします。そこから 1 を引いて「3+1-1」と
計算して、結果が 3 となります。これを 3 進数表記すると、そのまま「3」です。
G2 (3) の計算も同様ですが、今度は 3 の底を 4 の底に書き換えるので、
「3」の部分がそのまま「4」になっ
て、そこから 1 を引きます。G3 (3) の計算では、4 の底を 5 に書き換えますが、4 という数字はないのでそ
のまま「3」となり、1 を引いて 2 になります。
以下、同様に繰り返して、G5 (3) で 0 に達して数列が終了します。
グッドスタイン数列は、0,1,2,3 から始まる時にはすぐに終わってしまいますが、4 以上からスタートする
となかなか終わらず、数列の値が急激に上昇します。Wikipedia には、19 から始まるグッドスタイン数列
の例が記されています。そこでは、G7 (19) = 4.3 × 10369693099 となっています。なぜ、G(3) の時のように
すぐに終わらないのでしょうか。
2
G0 (19) =
19 = 22 + 2 + 1
G1 (19) =
33 + 3 + 1 − 1 = 33 + 3 = 7625597484990
G2 (19) =
44 + 4 − 1 = 44 + 3
G3 (19) =
55 + 2
G4 (19) =
66 + 1
G5 (19) =
77
3
4
3
4
5
6
7
ここまでは、数字は増えますが表記は大人しく下がっています。この次の段階で、表記が爆発します。G6 (19)
7
8
8
は、77 の 7 を 8 に書き換えて 88 にしてから、1 を引きます。88 − 1 を 8 を底とする遺伝的表記をする
と、とても書き切れない数になります。8 を 10 に変えて 1010
れは 9 が 10
10
個続く 10
10
10
− 1 を 10 進数表記することを考えると、こ
桁の数になります。そしてさらに、一番上の桁は指数部分が 9999999999 となっ
8
て、これもまた 10 桁の数なので、さらに 10 進数で分解する必要があります。88 − 1 の場合は、88 桁の非
常に長い数列ができます。
G6 (19) の末尾は、· · · 7 × 82 + 7 × 8 + 7 となっています。ここから先は、底が 8, 9, 10, … と増えて行
き、同時に 1 を引かれることで、一番最後の 7 が 6, 5, 4, … と 1 ずつ引かれていって、G13 (19) に達したと
39 The
Goodstein sequence G(3) https://oeis.org/A215409
2.7. 原始帰納関数
23
ころで、· · · 7 × 152 + 7 × 15 と定数項が落ちます。次に、16 を底として書き換えて · · · 7 × 162 + 7 × 16 か
ら 1 を引く時に、7 × 16 − 1 = 111 を 16 進数で書いて 6 × 16 + 15 となり、今度は 15 が 0 になるまで続け
ますが、そうこうしているうちに底がどんどん大きくなり、1 を引くだけでは間に合わないのでどんどん急
激に値が増加して行きます。
さて、このように急速に増加するグッドスタイン数列ですが、必ずいつかは 0 となって終了する事が証明さ
れています。そこが、面白い所です。したがって、この数列が終了するまでのステップ数を関数と考えることが
できます。n から始まるグッドスタイン数列が終わるまでのステップ数を G(n) とします。数列は必ず終了する
ので、このように定義出来ます。この関数は、とても増加率の高い関数になります。G(4) = 3×2402653211 − 3
と計算されていますが、G(5) の先は、正確な値が計算されていません。最小と最大の見積もりが Googology
Wiki に記されています。最小の見積もりを見ると、
G(5) > (10 ↑↑ (10 ↑↑ (10 ↑↑ (10 ↑ 10 ↑ 10 ↑ 20)))
G(6) > (10 ↑↑↑↑)5 (10 ↑↑↑)5 (10 ↑↑)5 )(10 ↑ 10 ↑ 10 ↑ 10 ↑ 10 ↑ 117)
となり、G(5) ですでにトリトリを超えています。トリトリ回以上の繰り返しということになると、まとも
に計算しても終わるはずがありません。G(6) でヘキセーションのレベルに到達し、G(7) では↑を７つ重ね
る計算になり、G(8) では原始帰納では書けないような大きな数になって、そこから先は、さらに急速に増
加して行きます。
この関数の面白いところは、数列の定義はおとなしい原始帰納の定義なのに、定義された関数は原始帰
納よりもずっと増加率の高い関数になるところです。それでは、どの程度増加率の高い関数になるのでしょ
うか。この関数は原始帰納関数ではないので、後の章で検証をします。
2.7
原始帰納関数
四則演算しか知らない人が、巨大数を作るとしたら、たとえば「99999 × 99999」とか「999999 × 999999
× 99999」などと書くでしょう。ところが、このようにしてたくさん 9 を並べて、×をいっぱい使って数を
書いたところで、
「1010
1000
」にはかないません。
「1010
1000
」ほどの数を作るためには、101000 桁ほどの数字
やかけ算記号を書く必要があるからです。これは、四則演算によって作られる関数よりも、べき乗関数の
方が増加率が飛躍的に高いためです。さらに、クヌースの矢印表記という新しい関数を取り入れることで、
べき乗などの表現をいくら使っても書き表せないほどの大きな数を作ることができました。
このように、より増加率の高い関数を定義することで、より巨大な数を作ることができるため、巨大数
を作ることは巨大関数を作る事と同じことになります。今後は、いかにして巨大関数を作るか、という議論
が中心になります。それはそのまま、巨大数を作る、ということになります。したがって、本書のタイトル
も「巨大関数論」とする方が内容に即していますが、巨大数への想いを込めて、あえて「巨大数論」としま
した。
さて、巨大関数を作っても、作った巨大関数がどの程度の大きさなのかを評価できないと、どれだけ巨大
な関数を作ったのかが分かりません。そこで、関数の性質を調べるためには、数学的な知識が必要となり
ます。
第 2 章 原始帰納関数
24
本章でこれまでに紹介した関数は、グッドスタイン関数を除けば、すべて 原始帰納関数 （あるいは
原始再帰関数 ; Primitive recursive function）40 になります。原始帰納関数とは、３つの基本関数と２
つの作用素（合成と原始帰納）を繰り返して作られる関数で、以下のように定義されます。
【定義】原始帰納関数
原始帰納関数とは、定義域と値域が非負整数である非負整数個の引数をとる関数で、引数に対し、
1. ゼロ関数 (zero function): f (x1 , …, xn ) = 0
2. 後者関数 (successor function): f (x) = x + 1
3. 射影関数 (projection function): 複数の引数を持つ関数から、i 番目の引数を返す関数
f (x1 , …, xn ) = xi
4. 合成作用素 (composition operator): f と g の合成関数 h
h(x1 , ..., xm ) = f (g1 (x1 , ..., xn ), ..., gk (x1 , ..., xn ))
5. 原始帰納作用素 (primitive recursion operator): f と g の原始帰納関数 h
h(0, x1 , ..., xk ) = f (x1 , ..., xk ),
h(n + 1, x1 , ..., xk ) = g(h(n, x1 , ..., xk ), n, x1 , ..., xk )
以上の３つの関数と２つの作用素（操作）を有限回適用した関数である。
照井 (2005)
41
は、「いかに基本的であるとはいえ、原始再帰的関数のクラスは広大である。実際、数論
においてあらわれる関数（関係）や、コンピュータプログラマが取り扱う関数（関係）の大部分は原始再帰
関数である。にもかかわらず、後ほど例を挙げるように、全ての計算可能な関数が原始再帰的であるわけで
はない。」として、どのような関数が原始再帰的であるかを示してから、本書の次章以降で紹介するような
原始再帰的でない関数について議論しています。また、基本原始帰納操作の繰り返しから次のような操作も
構成できることが示されています。
1. 余剰項の追加 (weakening): f1 (x1 , …xn , y) = f (x1 , …xn )
2. 同一項の複数回使用 (contraction): f2 (x1 , …xn − 2, y) = f (x1 , …xn − 2, y, y)
3. 項の順番の入れ替え (exchange): f3 (x1 , …, xn − 2, y, z) = f (x1 , …, xn − 2, z, y)
4. 自由合成: 多変数関数で、変数の一部を合成する
5. 自由原始帰納: f,g が原始帰納関数ならば、次の関数 h も原始帰納である。
h(x1 , …, xn , 0) = f (z1 , …, zi )
h(x1 , …, xn , y + 1) = g(w1 , …, wj , y, h(x1 , …, xn , y))
ここで変数 z と w はそれぞれ x1 , …, xn のどれかで、下式右辺の再帰項 f (y, x1 , …, xn ) と後退項 y は
実際には何度あらわれてもよく、どの順でどこに現れても、どちらか一方が（または両方とも）あら
われていなくても良い。
以下は、照井 (2005) に紹介されている原始帰納関数の例です。
40 後藤滋樹教授の講義資料
41 照井一成
(PDF) http://www.goto.info.waseda.ac.jp/˜goto/infomath/infomath-5-induction.pdf
(2005)「再帰的関数論」 http://www.kurims.kyoto-u.ac.jp/˜terui/mita05.pdf
2.7. 原始帰納関数
25
1. 定数関数 f (x1 , …, xn ) = p
2. 加算 x + y
3. 乗算 xy
4. べき乗 xy
5. 階乗 x!
6. 大小関係 x < y や同値関係 x = y を判定する関数
7. 素数を判定する関数
8. n 番目の素数を返す関数
9. 以上を繰り返した関数
基本関数と操作の組み合わせでどのように上記の関数を生成するのかは、照井 (2005) に詳しく議論され
ていますが、ここでは概略を説明します。定数関数は、ゼロ関数に後者関数を繰り返し適用することで生成
出来ます。ゼロ関数の変わりに定数関数を基本関数とすることもあります。加算 plus は、後者 suc と plus
の原始帰納を繰り返すことで、plus(x, 0) = 0, plus(x, y + 1) = suc(plus(x, y)) と計算出来ます。つまり、
後者関数 (+1) を y 回繰り返す、という関係を原始帰納で計算出来ます。同様に、乗算 times は加算を繰り
返すので、加算の原始帰納 times(x, y + 1) = plus(x, (x, times(x, y)) で計算出来ます。べき乗は、乗算の繰
り返しなので同様に計算出来ます。階乗も乗算の繰り返しなので、繰り返し方を工夫すれば原始帰納で計算
出来ます。
さらに、原始帰納で大小関係の比較や同値関係の判定もできるため、x は y の約数であるかどうかという
判定ロジックも原始帰納となり、約数が存在するかどうかを調べる素数判定も原始帰納になります。した
がって、素数かどうかを順番に調べることで、n 番目の素数も原始帰納で計算出来ます。このように、原始
帰納の範囲は非常に広く、色々な計算ができます。
後者の原始帰納で加算を、加算の原始帰納で乗算を、乗算の原始帰納で冪乗を計算することができまし
た。これは、ハイパー演算子で言えば、ハイパー 0 の原始帰納からハイパー 1 を、ハイパー 1 の原始帰納
からハイパー 2 を、ハイパー 2 の原始帰納からハイパー 3 を計算したことになります。したがって、ハイ
パー 3 の原始帰納からハイパー 4 の超冪を計算できます。このように、原始帰納を繰り返すことで、ハイ
パー演算子が計算できます。つまり、クヌースの矢印表記は原始帰納で計算できます。
26
第3章
3.1
2 重帰納関数
アッカーマン関数
本章では 2 重帰納関数について議論しますが、2 重帰納関数の説明に入る前に、具体例として関数の値が
爆発的に大きくなることで有名な アッカーマン関数 (Ackermann Function)
1 2 3
を紹介します。
【定義】アッカーマン関数
非負整数 x,y に対し、以下のように定義される関数 A(x,y) をアッカーマン関数 (Ackermann’s Function)
とする。
A(0, y) = y + 1
A(x + 1, 0)
= A(x, 1)
A(x + 1, y + 1) = A(x, A(x + 1, y))
A(x,y) を、具体的に計算してみましょう。
A(1, 1)
= A(0, A(1, 0)) = A(0, A(0, 1)) = A(0, 2) = 3
A(1, 2)
= A(0, A(1, 1)) = A(0, 3) = 4
A(1, 3)
= A(0, A(1, 2)) = A(0, 4) = 5
A(1, y) = A(0, A(1, y − 1)) = A(1, y − 1) + 1 = 2 + y
A(2, 1)
= A(1, A(2, 0)) = A(1, 3) = 5
A(2, 2)
= A(1, A(2, 1)) = A(1, 5) = 7
A(2, 3)
= A(1, A(2, 2)) = A(1, 7) = 9
A(2, y) = A(1, A(2, y − 1)) = A(2, y − 1) + 2 = 2y + 3
A(3, 1)
= A(2, A(3, 0)) = A(2, 5) = 13
A(3, 2)
= A(2, A(3, 1)) = A(2, 13) = 29
A(3, 3)
= A(2, 29) = 61
A(3, y) = A(2, A(3, y − 1)) = 2 ∗ A(3, y − 1) + 3 > 2y
A(4, 1)
= A(3, A(3, 1)) = A(3, 13) > 213
A(4, 2) >
A(3, 213 ) > 2∧ 2∧ 13 > 2 ↑ 2 ↑ 2 ↑ 2 = 2 ↑↑ 4
A(4, 3) >
A(3, 2 ↑↑ 4) > 2 ↑ 2 ↑ 2 ↑ 2 ↑ 2 = 2 ↑↑ 5
A(4, y) > 2 ↑↑ (y + 2)
1 巨大数資料
wiki - アッカーマン関数 http://www51.atwiki.jp/largenumbers/pages/19.html
http://www.tandess.com/music/programming/ackerman.html
3 Wolfram MathWorld - Ackermann Function http://mathworld.wolfram.com/AckermannFunction.html
2 アッカーマン関数計算過程表示プログラム
3.1. アッカーマン関数
27
このように、A(4,y) は 2 のテトレーションとなることが分かりました。ここから先に進むには、2 のテト
レーションを 3 のテトレーションに変える必要がありますので、2 のテトレーションを Hypercalc で計算
します。
2 ↑↑ 4 =
65536 > 3 ↑↑ 2
2 ↑↑ 5 =
2.0035299306 × 10 ↑ 19728 > 3 ↑↑ 3
2 ↑↑ 6 =
10 ↑ (6.0312260633 × 10 ↑ 19727) > 3 ↑↑ 4
2 ↑↑ 7 =
10 ↑ 10 ↑ (6.0312260633 × 10 ↑ 19727) > 3 ↑↑ 5
2 ↑↑ 8 =
10 ↑ 10 ↑ 10 ↑ (6.0312260633 × 10 ↑ 19727) > 3 ↑↑ 6
となり、冪乗を繰り返すと右辺のかっこの中は変わらなくなり、3 ↑↑と増加の程度は等しくなるので、
2 ↑↑ x > 3 ↑↑ (x − 2)
と比較出来ます。したがって、
A(4, y) > 2 ↑↑ (y + 2) > 3 ↑↑ y
となります。このように、テトレーションの元を 2 から 3 に変換することで、以後計算を続けることがで
きます。まずは、A(5,y) がペンテーションになることを示します。
A(5, 1) =
A(4, A(4, 1)) = A(4, 213 ) > 3 ↑↑ 213 > 3 ↑↑↑ 2
A(5, 2) =
A(4, A(5, 1)) > 3 ↑↑ (3 ↑↑↑ 2) = 3 ↑↑↑ 3
A(5, 3) =
A(4, A(5, 2)) > 3 ↑↑ (3 ↑↑↑ 3) = 3 ↑↑↑ 4
A(5, y)
> 3 ↑↑↑ y
A(5,2) でトリトリを越えました。↑の数が増えても同様の計算ができるので、以下のようになります。
A(5, y)
> 3 ↑3 y
A(6, y)
> 3 ↑4 y
A(7, y)
> 3 ↑5 y
A(x, y)
> 3 ↑x−2 y
このように、x=1,2 の時は y に対して線形に増加し、x=1 の時は y の加算 (2+y)、x=2 の時は y の乗算
(2 × y) になります。x=3 の時は y に対して指数的に増加し、y の冪乗 (2y ) になります。x=4 の時は、指数
を重ねる↑↑ y の演算になり、x=5 の時は、↑↑↑ y の演算になります。こうして、変数 x を増やすこと
は↑を重ねる数を増やす効果を持つ事になります。
第 3 章 2 重帰納関数
28
3.2
2 重帰納関数
アッカーマン関数はどんな原始帰納関数よりも増加速度が大きい数です。つまり、任意の原始帰納関数
f (x) に対して、
f (x) < A(c, x)
(3.1)
となる c が存在します。それは、アッカーマン関数が 2 重帰納関数であるためです。そのことを、これから
示します。なお、ここでは 1 変数関数について議論を進めますが、f(x) が多変数関数であっても同様の議論
ができます。
前章の原始帰納の定義式において B(x) = h(n, x), C(y) = g(y, n, x) と書くと、
B(x + 1) = C(B(x))
B(x) = C x (B(0))
と書けます。つまり、B(x) は関数 B(0) に対して C(y) の合成を x 回繰り返した関数です。合成の回数を変
数とする関数を作ることが、原始帰納の操作となっています。このことを「操作を数え上げる」と表記する
こととします。すなわち、原始帰納の操作は合成操作を数え上げます。したがって、関数 f(x) から、合成
操作を有限回 (n 回) 繰り返して得られるいかなる関数 g(x) よりも、初期関数から原始帰納の操作によって
得られる関数 h(x) の方が大きくなります。たとえば、f(x) に f(f(x)) の合成操作を n 回繰り返して得られる
関数を gn (x) として、
g1 (x) = f 2 (x) : g1 (1) = f 2 (1), g1 (2) = f 2 (2), ..., g1 (n) = f 2 (n)
g2 (x) = f 3 (x) : g2 (1) = f 3 (1), g2 (2) = f 3 (2), ..., g2 (n) = f 3 (n)
…
gn (x) = f
n+1
(x) : gn (1) = f
n+1
(1), gn (2) = f
n+1
(2), ..., gn (n) = f
n+1
(n)
といった表を作ります。このとき、関数 f(x) に合成操作を x 回繰り返して得られる関数 gx (x) = f x+1 (x)
は、
gx (x) = f x+1 (x) : gx (1) = f 2 (1), gx (2) = f 3 (2), ..., gx (n) = f n+1 (n) と書く事ができて、これは上の表
において右辺を左上から右下へ対角線上に拾い上げています。
このように、操作の回数を数え上げることは対角線上に拾い上げて関数を作成する操作であることから、
「操作の対角化」という言葉が巨大数探索スレッドの中で使われています。これは、いわゆるカントールの
対角線論法と言われる論法です。
さて、アッカーマン関数の漸化式 (3.1) において、f (y) = A(x, y), g(y) = A(x + 1, y) とすると、
g(y + 1) = f (g(y)) となり、したがって、
g(y) = f y (g(0)) = f y (f (1)) = f y+1 (1) と書けます。すなわち、g(y) は関数 f(y) に対して合成を y 回繰
り返して 1 を代入した関数です。これは対角線ではありませんが関数の合成回数を数え上げています。関数
f n (y) と f ( y + 1)(1) を比べると、y > 10n において
f y+1 (1) = f n [f y−n+1 (1)] > f n [f 0.9y+1 (1)] > f n (y)
となるため、合成を有限回繰り返したいかなる関数よりも合成回数を数え上げる関数の方が大きくなり
ます。つまり、合成回数を数え上げることで、関数の対角列を取る「操作の対角化」と等しい効果が得られ
ます。
3.3. モーザー数
29
このように、f(y) から g(y) を生成する操作は、合成を数え上げる原始帰納操作となるため、A(x,y) に立
ち戻って考えると、A(x+1,y) は A(x,y) に対して原始帰納の操作を 1 回操作した関数です。このことから、
A(x,y) は A(0,y) に対して原始帰納の操作を x 回繰り返した関数であり、原始帰納の操作を数え上げていま
す。このように、原始帰納を数え上げる 2 重帰納 4 を、以下で定義します。
【定義】2 重帰納
原始帰納操作を数え上げる操作を 2 重帰納作用素（操作）とする。
2 重帰納関数 (double recursive function) とは、定義域と値域が非負整数である非負整数個の引数をと
る関数で、引数に対し、ゼロ、後者、射影、合成、原始帰納、2 重帰納の作用素（操作）を有限回適用
した関数である。ただし、その中で 2 重帰納操作を少なくとも 1 回含むものとする。
射影、合成、原始帰納の操作を n 回繰り返して作られた原始帰納関数 f(x) について、その中で最も関数の
増加度が大きい原始帰納の操作を n 回繰り返して作られた関数 A(n,y) は大きくなります。すなわち、x > n
において f (x) > A(x, y) ですから、A(x,y) は f(x) と比べて本質的に大きい、ということになります。
3.3
モーザー数
モーザーは、 スタインハウスの多角形表記 を元として、 モーザーの多角形表記 を作りました5
6
。多
角形の中に数字を入れる書き方をして、多角形を重ねることと、多角形の辺の数を増やすことで、大きな数
を作ります。まず、3 角形の中に x を書くことで、xx を表記します。ここでは、x 角形の中の y を m(x,y)
と書きます。
m(3, x) = xx = x ↑ x
次に、4 角形の中の x は、x 重の 3 角形の中に x が入っている数です。すなわち、
m(4, x) = m(3, m(3, …m(3, x)…))(m が x 個)
となります。そして、5 角形の中の x は、x 重の 4 角形の中の x です。スタインハウスは、4 角形の代わ
りに円を使ってここで終わりましたが、モーザーはそれを n 角形に拡張しました。この時、5 角形の中の 2
を メガ (mega) として、メガ角形の中の 2 を モーザー数 (moser) としました。
【定義】モーザー数
モーザーの多角形表記で、5 角形の中の 2 をメガとする。メガ角形の中の 2 をモーザー数とする。
モーザー数 = m(m(5,2),2)
2
メガの大きさは、m(3, 2) = 2 = 4
m(4, 2) = m(3, m(3, 2)) = m(3, 4) = 44 = 256
m(5, 2) = m(4, m(4, 2)) = m(4, 256)
となります。ここで、m(4,x) の計算は、冪乗の計算を x 回繰り返すので、テトレーションと同じ程度の
増加になります。テトレーションの場合には、xy の y の部分だけが大きくなるところ、m(4,x) では x と
y が同時に大きくなるので、厳密には m(4,x) の方が増加は速いのですが、x の部分を大きくすることは、
y を増加させることと比べるとたいして増加には寄与しないので、結局は同程度、ということになります。
Hypercalc で確認してみます。
4 ハイパー演算子（2
変数版）が原始帰納的であることの証明 http://d.hatena.ne.jp/mathsociety/20090927/1254079255
- 多角形表記 http://bit.ly/19ieGNU (ja.wikipedia.org)
6 MathWorld - Steinhaus-Moser Notation http://mathworld.wolfram.com/Steinhaus-MoserNotation.html
5 Wikipedia
第 3 章 2 重帰納関数
30
x1 = m(3, 256) = 256256
= 3.231700607153 × 10616 (クラス 2)
x2 = m(3, x1 ) = xx1 1
= 10 ↑ (1.992373902865 × 10619 ) (クラス 3)
x3 = m(3, x2 ) = xx2 2
= 10 ↑ 10 ↑ (1.992373902865 × 10619 ) (クラス 4)
x4 = m(3, x3 ) = xx3 3
= 10 ↑ 10 ↑ 10 ↑ (1.992373902865 × 10619 ) (クラス 5)
x5 = m(3, x4 ) = xx4 4
= 10 ↑ 10 ↑ 10 ↑ 10 ↑ (1.992373902865 × 10619 ) (クラス 6)
x6 = m(3, x5 ) = xx5 5
= 10 ↑ 10 ↑ 10 ↑ 10 ↑ 10 ↑ (1.992373902865 × 10619 ) (クラス 7)
3 ↑の繰り返しも、階乗の繰り返しも、xx の繰り返しも、すべてある段階以上は 10 ↑の繰り返しと同じ
で、右肩の数字はびくともしなくなります。この計算から、
m(4, 256) = x256 = 255 P T (1.992373902865 × 10619 ) (クラス 257)
と、メガの値が分かります。
m(x,y) は、A(x,y) と同様に増加する 2 重帰納関数です。m(4,x) は↑↑つまりテトレーションに相当す
るのと同様に、m(5,x) はペンテーションに相当し、m(x,y) は、ハイパー x 演算子、つまり ↑x−2 に相当し
ます。ここで、x を 1 つ増やす効果が原始帰納で、その回数を数え上げることが 2 重帰納なので、たとえば
x=5 と固定した時には、原始帰納ですが、x を変数とすると 2 重帰納になります。したがって、メガは原始
帰納ですが、m(x,y) の x にとても大きな数を代入したモーザー数は、2 重帰納です。
3.4
グラハム数
1971 年に、グラハム・ロートシルト7 は「n 次元の超立方体の合計 2n 個の頂点を総て結び、それを赤と
青の二色の何れかに塗る。 このとき n が充分大きいならば, どのような塗り方をしても, 必ず同一平面上
にある四点でそれらを結ぶ線が総て同一の色であるものが存在する」という定理を発表しました。この定
理の中の「十分大きい n」の 1 つがグラハム数です。 グラハムは論文で、そのような数の例として、以下
のような数字を示しました。
F (1, n)
F (m, n)
N
=
2n , F (m, 2) = 4, m ≥ 1, n ≥ 2,
= F (m―1, F (m, n―1)), m ≥ 2, n ≥ 3.
≤ F (F (F (F (F (F (F (12, 3), 3), 3), 3), 3), 3), 3)
これは非常に大きい数字ですが、その後、ガードナー8 とグラハムが 1977 年にさらに大きな数を上限とし
て発表しました。この論文で発表された数字が、 グラハム数 (Graham’s number)
9 10 11
として有名に
なりました。これは、グラハムが 1971 年に論文で発表した数字よりもさらに大きいものです。
【定義】グラハム数
f (x) = 3 ↑...(x 個)...↑ 3 としたときの f 64 (4) を、グラハム数とする。
7 Graham,
R. L. and Rothschild, B. L. ”Ramsey’s Theorem for n-Parameter Sets.” Trans. Amer. Math. Soc. 159,
257-292, 1971. http://www.ams.org/journals/tran/1971-159-00/S0002-9947-1971-0284352-8/
8 Martin Gardner https://en.wikipedia.org/wiki/Martin Gardner
9 裏サンデー「寿司 虚空編」第 1 話 http://urasunday.com/u-2 09/comic/001 001.html
10 巨大数資料 wiki - グラハム数 http://www51.atwiki.jp/largenumbers/pages/5.html
11 Wolfram MathWorld - Graham’s Number http://mathworld.wolfram.com/GrahamsNumber.html
3.5. コンウェイのチェーン表記
31
グラハム数の定義において、f (x) は↑の個数を数え上げる 2 重帰納で、f 64 (4) の計算は関数 f (x) に対す
る原始帰納です。したがって、グラハム数は 2 重帰納に原始帰納を重ねた数で、2 重帰納です。グラハム数
の大きさは、次に紹介するコンウェイのチェーン表記を使うと評価出来ます。
3.5
コンウェイのチェーン表記
矢印表記を一般化した コンウェイの矢印チェーン表記 (Conway’s chained arrow notation)
の定義を、以下に記します。
12 13 14 15
【定義】コンウェイのチェーン表記
基本的な定義 (3 つの数字が並んでいる場合) は以下のとおりです。
a ↑...(c 個)... ↑ b = a → b → c
さらに、以下のように、4 つ以上の数字を連ねて書くことができます。
チェーンの最後の数が 1 のときはこれを落とすことができます。
a → b →... → x → y → 1 = a → b →... → x → y
チェーンの最後から 2 番目の数が 1 の場合、これと最後の数をまとめて落とせます。
a → b →... → x → 1 → z = a → b →... → x
次のような変形によって最後とその前の数を減らすことができます。
a → b →... → x → y → z = a → b →... → x → (a → b →... → x → y-1 → z) → z-1
このチェーンは、とても増加率の高い関数です。まず、3 つの変数の場合は、
10 → 3 → 2 =
10 ↑↑ 3 = 10 ↑ 10 ↑ 10 は、グーゴルより大きく不可説不可説転よりも小さい数
10 → 5 → 2 =
10 ↑↑ 5 = 10 ↑ 10 ↑ 10 ↑ 10 ↑ 10 は、第 2 スキューズ数よりも大きな数
3→3→3 =
3 ↑↑↑ 3 = トリトリ
となります。クヌースの矢印表記で書くことのできる原始帰納程度の数は、3 変数チェーンで表記できる
程度の大きさとなります。
グラハム数は、f (x) = 3 ↑↑↑...(x 個)...↑ 3 = 3 → 3 → x としたときの f 64 (4) です。
3 → 3 → 1 → 2 = 3 → 3 → 1 = f (1) = 27
3 → 3 → 2 → 2 = 3 → 3 → (3 → 3 → 1) = f 2 (1) = f (27)
3 → 3 → 3 → 2 = 3 → 3 → (3 → 3 → 2 → 2) = f 3 (1) = f 2 (27)
3 → 3 → n → 2 = f n (1) = f n−1 (27)
3 → 3 → 64 → 2 = f 64 (1) < f 64 (4) = グラハム数
3 → 3 → 65 → 2 = f 64 (27) > f 64 (4) = グラハム数
12 巨大数資料
wiki - チェーン表記 http://www51.atwiki.jp/largenumbers/pages/9.html
J. H. and Guy, R. K. (1996) ”The book of Numbers” p. 61-62 http://bit.ly/11ikm9t (at www.futuretg.com)
14 Big numbers (Susan Stepney) http://www-users.cs.york.ac.uk/ susan/cyc/b/big.htm
15 Large Numbers p.4 (Robert Munafo) http://www.mrob.com/pub/math/largenum-4.html
13 Conway,
第 3 章 2 重帰納関数
32
したがって、
3 → 3 → 64 → 2 ＜グラハム数＜ 3 → 3 → 65 → 2
となります。
3 → 3 → 3 → 3 = 3 → 3 → (3 → 3 → 2 → 3) → 2 > 3 → 3 → 65 → 2
となります。
次に、モーザー数と比較します。メガ m(x,2) は↑が x-2 連なる効果と同じなので、3 → 3 → x-2 程度の
大きさになります。この見積もりだと、メガは 3 → 3 → 3、つまりトリトリ程度となって、若干大き過ぎる
気もしますが、その程度のおおざっぱな見積もりです。f(3)=3 → 3 → 3=トリトリなので、メガよりも f(3)
の方が大きい数です。モーザー数の大きさを評価すると、このように計算出来ます。
3 → 3 → 2 → 2 = 3 → 3 → 27
<
3 → 3 → m(5, 2) ≈ モーザー数
<
3 → 3 → f (3)
<
3 → 3 → f (27)
=
3→3→3→2
つまり、↑を 27 個並べる程度の 3 → 3 → 2 → 2 は原始帰納の範囲に入りますが、↑を f(27) 個並べる 3
→ 3 → 3 → 2 は、モーザー数を越える 2 重帰納になっています。以上をまとめます。
チェーンによる巨大数の比較
無量大数
< 10 → 3 → 2 = 1010
10
< 不可説不可説転 < 10 → 4 → 2 = 1010
1010
< 第 2 スキューズ数 < 10 → 5 → 2 (ここまでハイパークラス 1)
< トリトリ = 3 → 3 → 3 (ハイパークラス 2)
< 3 → 3 → 2 → 2 = 3 → 3 → 27 (ここまで原始帰納)
< モーザー数 (ここから 2 重帰納)
< 3 → 3 → 3 → 2 = f 3 (1)
< 3 → 3 → 64 → 2 = f 64 (1)
< グラハム数 < 3 → 3 → 65 → 2
< 3→3→3→3
このように、チェーンの最後の数を増やすこと、そしてチェーンそのものを伸ばすことにより、増加度が
加速度的に増す関数がチェーン表記です。
3.6. ここまでのまとめ
33
チェーン表記は、2 重帰納関数です。
まず、3 変数のチェーンについては
a ↑...(c 個)... ↑ b = a → b → c
と定義されますので、タワーの定義式
x ↑↑↑ y = x ↑↑ (x ↑↑↑ (y - 1))
をチェーンで表記すると、
x → y → 3 = x → (x → (y-1) → 3) → 2
と、多変数の定義式と同じになります。
したがって、チェーンの基本計算式は、多変数のこの式となります。
a → b →... → x → y → z = a → b →... → x → (a → b →... → x → y-1 → z) → z-1
ここで、アッカーマン関数
A(x+1,y+1) = A(x,A(x+1,y))
について、x+1 = z, y+1 = y として変数の順番を交換し、
(y,z) = A(A(y-1,z), z-1)
さらに定数項 a,b,...,x を加えると
A(a,b,...,x,y,z) = A(a,b,...,x,A(y-1,z), z-1)
となってチェーンの式と一致することから、チェーンの漸化式はアッカーマンと同じ 2 重帰納の式です。
したがって、チェーン表記は 2 重帰納をたくさん繰り返す 2 重帰納関数である、ということになります。
チェーンでは、矢印を 1 つ伸ばすこと、すなわち、変数を 1 つ増やすことで、基本 2 重帰納操作を 1 回す
ることになります。変数が n 個のチェーンでは、基本 2 重帰納操作が n-2 回行われます。
3.6
ここまでのまとめ
ここまでのポイントをまとめます。
1. 操作の一定数回の繰り返しよりも、操作の数え上げの方が強い関数を生成する。
2. 合成操作を数え上げると原始帰納となる。したがって、原始帰納の操作は合成操作よりも強い。
3. 原始帰納操作を数え上げると 2 重帰納となる。したがって、2 重帰納の操作は原始帰納操作よりも強い。
4. アッカーマン関数は 2 重帰納関数である。
5. チェーン表記は 2 重帰納をたくさん繰り返す 2 重帰納関数である。変数が n 個のチェーンでは、基本
2 重帰納操作が n-2 回行われる。
6. 第 2 スキューズ数 < 3 → 3 → 3 < モーザー数 < グラハム数 < 3 → 3 → 3 → 3
34
第 4 章 多重帰納関数
4.1
多重帰納
前章までの内容は、一般的に知られている知識がほとんどです。本章の内容は、主として巨大数探索ス
レッドで議論されて来た内容です。
原始帰納、2 重帰納の定義を拡張して、 n 重の多重帰納関数 (multiply recursive function) をこのように
定義します。
【定義】多重帰納
n-1 重帰納操作を数え上げる操作を n 重帰納作用素（操作）とする。
n 重の多重帰納関数 (multiply recursive function) とは、定義域と値域が非負整数である非負整数個の
引数をとる関数で、引数に対し、ゼロ、後者、射影、合成、原始帰納、2 重帰納、3 重帰納、...、n 重帰
納の作用素（操作）を有限回適用した関数である。ただし、その中で n 重帰納操作を少なくとも 1 回
含むものとする。
4.2
多変数アッカーマン関数
巨大数探索スレッド 7 で、たろう氏によって、アッカーマン関数の拡張 多変数アッカーマン関数
以下のように定義されました。
1 2
が
【定義】多変数アッカーマン関数
n 個の非負整数を引数として以下のように定義される関数 A を n 変数アッカーマン関数とする。
A(□, a) =
A(Ｘ, b + 1, 0, □, a) =
A(Ｘ, b + 1, 0) =
A(Ｘ, b + 1, a + 1) =
a+1
A(Ｘ, b, a, □, a)
A(Ｘ, b, 1)
A(Ｘ, b, A(Ｘ, b + 1, a))
ただし、a, b : 0 以上の整数, □ : 0 個以上の 0, Ｘ : 0 個以上の 0 以上の整数
最後の 2 式により、右から 2 個目の変数は原始帰納、その数え上げが 2 重帰納となります。2 式目が、多
重帰納を定義する肝となります。□に含まれる 0 の数を n とすると、b の項は右から n+3 番目となります。
n=0 の時は、 次に示す 3 変数アッカーマンの式と一致します。つまり、右から 3 変数目の b を 1 つ増やす
1 巨大数探索スレッド
2 Googology
7-571 でアップされた文書 (たろう, 2007 年 10 月 17 日) http://gyafun.jp/ln/archive/7-571.txt
Wiki の記述 http://googology.wikia.com/wiki/Taro’s multivariable Ackermann function
4.3. 多重帰納に見えてそうでない関数
35
操作が、右から 2 変数目に変数 a を用いた 2 重帰納の操作となり、右から 3 変数目が 2 重帰納を数え上げ
る 3 重帰納となります。このようにして、右から n+2 番目の項が n+1 重帰納であり、右から n+3 番目の
b の項は、右から n+2 番目の n+1 重帰納を数え上げる (変数 a 回の操作をする) ことで n+2 重帰納の操作
となります。したがって、n 変数アッカーマン関数の 1 番左の項は、n-1 重帰納となり、それを変数に持つ
n 変数アッカーマン関数は n 重帰納関数となります。
多変数アッカーマン関数の例として、3 重帰納の 3 変数アッカーマン関数を以下の様に書くことができ
ます。
【定義】3 変数アッカーマン関数
非負整数 x,y,z に対し、以下のように定義される関数 A(x,y,z) を 3 変数アッカーマン関数とする。
A(0, 0, z) =
z+1
A(x + 1, 0, z) =
A(x, z, z)
A(x, y + 1, 0) =
A(x, y, 1)
A(x, y + 1, z + 1)
=
A(x, y, A(x, y + 1, z))
ただし、後述するように、これはアッカーマンオリジナルの 3 変数アッカーマン関数とは異なる。
この 3 変数アッカーマン関数が、2 重帰納を数え上げる 3 重帰納操作を含み、したがってどんな 2 重帰納
関数よりも大きい 3 重帰納関数であることを示します。
2 変数アッカーマンの定義と見比べることにより、A(0,y,z)=A(y,z) が成り立ちます。また、Ax (y, z) =
A(x, y, z) とすると、
Ax (0, z) = Ax−1 (z, z)
Ax (y + 1, 0)
= Ax (y, 1)
Ax (y + 1, z + 1) = Ax (y, Ax (y + 1, z))
となり、Ax−1 (z, z) から Ax (z, z) を生成する操作は、2 重帰納操作となります。
したがって、A(x, y, z) = Ax (y, z) は、関数 A(0, 0, z) = z + 1 に対して 2 重帰納操作を x 回繰り返した関
数であり、これは 2 重帰納操作を数え上げる 3 重帰納関数です。
4.3
多重帰納に見えてそうでない関数
2 重帰納も多重帰納の一種ですが、この節に限って 3 重帰納以上を多重帰納とします。チェーンの定義
は、一見すると多重帰納に見えますが、2 重帰納の章で示した様に、2 重帰納操作を繰り返した 2 重帰納関
数です。一方、前節で示した様に、適切に n 変数アッカーマン関数を定義する事で、n 重帰納関数を作るこ
とができます。ここで、n 重帰納関数はいかなる n-1 重帰納関数よりも大きい、という明確な強弱関係を持
ちます。
アッカーマン関数のアッカーマンによるオリジナルの定義は
A(x, y, 0) =
x+y
A(x, 0, 1) = 0
第 4 章 多重帰納関数
36
A(x, 0, 2) =
1
A(x, 0, z) =
x
A(x, y, z) =
A(x, A(x, y − 1, z), z − 1)
というもので、3 変数でした。これに対して、様々な 2 変数バージョンが考えられて、その中で Peter and
Robinson が前章で紹介した形の 2 変数アッカーマン関数を作成しました。アッカーマンが考えたオリジナ
ルの 3 変数アッカーマン関数は、前章の 2 変数アッカーマン関数と同じ程度の増加率を持つ 2 重帰納関数
です。通常、3 変数のアッカーマン関数と言えばこのアッカーマンのオリジナルの定義を意味しますが、本
書ではたろう氏が定義した多変数アッカーマン関数の定義にしたがった、3 重帰納のアッカーマン関数を 3
変数アッカーマン関数とします。
チェーン表記のように、一見、多重帰納のように見えてそうでない関数には、他にはたとえばこのよう
な関数があります。
A(0, 0, z)
= z+1
A(0, y + 1, 0) =
A(0, y, 1)
A(0, y + 1, z + 1)
=
A(0, y, A(x, y + 1, z))
A(x + 1, y + 1, z + 1)
=
A(x, A(x + 1, y, z + 1), A(x + 1, y, z + 1))
この式は、このように計算されます。
A(x + 1, y + 1, z + 1)
= A(x, A(x + 1, y, z + 1), A(x + 1, y, z + 1))
= A(x − 1, A(x, A(x + 1, y, z + 1) − 1, A(x + 1, y, z + 1)), A(x, A(x + 1, y, z + 1) − 1, A(x + 1, y, z + 1)))
= ...
= A(0, A2, A2) (A2 は x, y, z の 2 重帰納関数)
= A(A2, A2)
このように、A(x,y,z) の計算は 2 重帰納です。3 項漸化式において、このように最初に x を減らして、次に
y を減らすという計算方法では、2 重帰納どまりです。一方、3 変数アッカーマン関数では、最初に y を減
らして、y が 0 に到達してはじめて x を減らすことができます。そのために、x を 1 減らす計算が y を減ら
す計算を数え上げることができます。この計算順序の違いが、2 重帰納か 3 重帰納かの差を生んでいます。
このことが、多重帰納関数の計算を理解する上では重要です。
4.4
チェーンの長さを変数化
(a + 1) →…(a + 1) → (z + 1) → (y + 1) と a + 1 が x 個続くチェーンを fa (x, y, z) とします。
チェーンの定義から
fa (0, 0, z) =
fa (x + 1, 0, z) =
az
fa (x, z, a)
4.5. ふぃっしゅ数バージョン 1
37
fa (x + 1, y, 0) =
fa (x, y + 1, z + 1)
=
fa (x, 0, a)
fa (x, y, fa (x, y + 1, z))
となります。fa (x, y, z) と A(x,y,z) を比べると、若干異なるものの、同程度の増加度の関数となることが
分かります。チェーンを 1 個伸ばす (変数の数を増やす) ことは、A(x,y,z) において x を 1 つ増やすことに
相当します。そして、チェーン長が変数化された fa (x, y, z) は 3 重帰納です。
前章において、n 変数チェーン表記は、n-2 回の 2 重帰納操作を含む 2 重帰納関数である事が示されまし
た。そのことと、上記の計算から、A(x,y,z) は 2 重帰納操作を x 回施した x+2 変数チェーン表記に相当す
る大きさの関数となります。したがって、A(3,3,3) という数は、2 重帰納を 3 回繰り返した 5 変数チェーン
表記に相当する大きさとなり、4 変数表記の 3 → 3 → 3 → 3 よりも大きくなります。
4.5
ふぃっしゅ数バージョン 1
ここから、著者が考案した ふぃっしゅ数 の説明に入ります。
ふぃっしゅ数とは何か？それは、単純に「大きな数を作ろう」として作られた数です。グラハム数は、数
学の証明で用いられた数なので、実用的な目的がありました。ふぃっしゅ数には、実用的な目的は何もあり
ません。使い方としては「とにかく大きな数」を表すときに使える、というだけです。
「とにかく大きな数」
を言いたいのであれば、それが無量大数であっても不可説不可説転であっても、グラハム数であっても良
く、新たに「ふぃっしゅ数」などというものを作る必要はありません。それでは、なぜそんな数を考案した
のでしょうか。
そもそものきっかけは、大きな数を作ろう!ということでした。2ch のスレッドでは、たとえば、グラハ
ム数を使って以下の様な数が定義されました。
161 名前：１３２人目の素数さん ：02/06/20 22:25
>> 156 じゃあグラハム数でいってみよう
グラハム数の定義はご存知だと思うが 3 ↑↑↑↑ 3（これがどれだけ超巨大かはグラハム数ス
レ参照）の数だけ 3 と 3 の間に↑が挟まった数を 1 段階として、2 段階は 1 段階の数だけ 3 と 3
の間に↑がある数と繰り返した 63 段階目の数がグラハム数と定義されてる。
この前段階の数だけ↑が挟まる数が次の段階という 63 回の変換の 1 回をＧ変換と名付ける。
Ｎ０１ グラハム数回だけＧ変換した数回変換した数回変換した∼この繰り返しを
Ｎ０２ グラハム数回だけＧ変換した数回変換した数回変換した∼この繰り返しを
Ｎ０３ グラハム数回だけＧ変換した数回変換した数回変換した∼この繰り返しを
Ｎ０４ グラハム数回だけＧ変換した数回変換した数回変換した∼この繰り返しを
とやっていって、Ｎｏがグラハム数回まで到達したら終り
‥‥だけだと面白くないので 第 4 章 多重帰納関数
38
このＮｏの繰り返しをグラハム数回のＧ変換した数回変換した数回変換した
∼この繰り返しをグラハム数回のＧ変換した数回変換した数回変換した
上と同じく 1 行目がＮ 01、2 行目がＮ 02 としてＮ 0 グラハム数までいって終了 ‥‥だけだと面白くないので このＮ 0 の繰り返しをグラハム数回のＧ変換した数回変換した数回変換した
∼この繰り返しをグラハム数回のＧ変換した数回変換した数回変換した
上と同じく 1 行目がＮＯ 1、2 行目がＮＯ 2 としてＮＯグラハム数までいって終了
以上のように延々繰り返してＮＯの種類がグラハム数種類に到達した時の数 これに対して、このように大きな数を定義するプロセスを追う事で、グラハム数を定義の中で用いずに、
さらにグラハム数よりも大きな数、上記の数よりも大きな数を定義しよう、という目的で、以下の様な考察
がされました (2ch 過去ログ3 の 317-319 の発言)。
これまでの書き込みで「いかにして大きな数を作るか」というプロセスを一般化すると、大き
な数と増加の程度が大きい関数を生み出していくプロセスだと表現できる。
たとえば、
「m という数に f(x) という変換を n 回繰り返す」という表現をするときに、m,f(x),n
に使えるのは今までに定義された数と関数のみ。そこで、数と関数を双方ともに帰納的に定義
していくプロセスを追っていくことにする。
そこで、自然数 m と関数 f(x) のペアから、自然数 n と関数 g(x) のペアを生み出す変換（写
像）を
S:[m,f(x)] → [n,g(x)]
と表記することにすると、たとえば３↑↑↑↑３は、自然数４と、f(x)=３（↑が x 個）３から
f(4) とあらわされる。３↑↑↑↑３個だけ↑がはさまった数、は f(f(4)) である。したがって、
これを 64 回繰り返した数は f 64 (4) となり、この操作は g(x) = f 64 (x) という関数を自然数 64
と関数 f(x) から生み出す操作にほかならないため、
S : [m, f (x)] → [f m (m), f m (x)]
と書くと、m=64,f(x) からグラハム数よりも大きい f 64 (64) という数が生み出される。
これまでのスレッドにかかれた数は、いろいろなタイプの S 変換を数回、>> 161 でもせい
ぜい 10 回程度行っているにすぎない。S 変換については、上記の S 変換よりも、Ackermann タ
イプの S 変換の方がより関数を増加させる。
3 2ch 過去ログ
- 一番でかい数だした奴が優勝 (ふぃっしゅ数の提起) http://www.geocities.co.jp/Technopolis/9946/log/ln023.html
4.5. ふぃっしゅ数バージョン 1
39
そこで、これから先は「いかにしてより大きな数、関数を生み出す S 変換を作り出すか（こ
れを「より大きいＳ変換」と呼ぶ」といった考察をする。
その第１段階として、Ackermann 関数にならい、
B(0, n) = f (n)
B(m + 1, 0)
= B(m, 1)
B(m + 1, n + 1) = B(m, B(m + 1, n))
g(x) = B(x, x)
としたときに、
S : [m, f (x)] → [g(m), g(x)]
とする。少なくとも、これ以上に大きいＳ変換はこれまでにあらわれていない。したがって、た
とえば [3,f(x)=x+1] にこの S 変換を 10 回ほど繰り返せば、ゆうに >> 161 を越える。
では、この S 変換をさらに大きくするにはどうすれば良いか。
それには、S 変換を f(m) 回繰り返した変換を S2 変換とすれば良い。すなわち、m,f(x),S から
さらに大きな S2 変換を生み出すことができる。このプロセスを、
SS : [m, f (x), S] → [n, g(x), S2]
ただし g(x) = S2[m, f (x)], n = g(m)
という SS 変換で記述することにする。
[3,x+1,S] に SS 変換を 1 回かけると、S 変換を 4 回くりかえす変換が得られ、さらにもう 1 回
かけると、S 変換を大変な数繰り返した変換が得られるため、２回くりかえしただけで、すで
にこのスレッドに登場したいかなる有限の数よりも大きな数が得られる。
この発言の直後に、ふぃっしゅ数が定義されています。このように、数と関数から数と関数を生成する「S
変換」という概念を導入する事で、巨大数を生み出そうとしたのがふぃっしゅ数です。これがふぃっしゅ数
の定義です。
第 4 章 多重帰納関数
40
【定義】ふぃっしゅ数バージョン 1
[1] 自然数と関数のペアから、自然数と関数のペアへの写像 S（S 変換）を以下で定義する。
S : [m, f (x)] → [g(m), g(x)]
ただし g(x) は以下で与えられる。
B(0, n)
= f (n)
B(m + 1, 0) = B(m, 1)
B(m + 1, n + 1)
g(x)
= B(m, B(m + 1, n))
= B(x, x)
[2] 自然数、関数、Ｓ変換から同様の組を生み出す写像 SS を以下で定義する。
SS : [m, f (x), S] → [n, g(x), S2]
ただし S2 と n,g(x) は順次以下で与えられる。
S2
=
S f (m)
S2
:
[m, f (x)] → [n, g(x)]
[3] [3,x+1,S] に SS 変換を 63 回繰り返して得た自然数をふぃっしゅ数、関数をふぃっしゅ関数とする。
ここから先、色々なバージョンのふぃっしゅ数が登場することになるため、このふぃっしゅ数を「ふぃっ
しゅ数バージョン 1」と名付けます。また、ふぃっしゅ数バージョン 1 を F1 、ふぃっしゅ関数バージョン 1
を F1 (x) とします。一般に、ふぃっしゅ数バージョン N を FN 、ふぃっしゅ関数バージョン N を FN (x) と
表記します。
その後、ふぃっしゅ数の大きさが計算されました。同スレッドの 329,331,377-379 の計算内容を転記します。
[3,f(x)=x+1] にＳ変換を 1 回すると、
B(0, n) = n + 1
B(m + 1, 0) = B(m, 1)
B(m + 1, n + 1)
= B(m, B(m + 1, n))
g(x) = B(x, x)
となるので、B(m,n) はアッカーマン関数と一致し、g(x) = A(x, x) となるため、
S : [3, x + 1] → [A(3, 3), A(x, x)]
となる。
A(3, 3) = 61 なので4 、Ｓ変換 1 回ではまだたいした大きさにはならない。
4 裏サンデー「寿司 虚空編」第
2 話 http://urasunday.com/u-2 09/comic/002 001.html
4.5. ふぃっしゅ数バージョン 1
41
Ｓ変換の 2 回目。今度は、
B(0, n) = A(n, n)
B(m + 1, 0) = B(m, 1)
B(m + 1, n + 1)
= B(m, B(m + 1, n))
g(x) = B(x, x)
となるが、この g(x) 関数はとてつもない関数になる。
g(1) =
B(1, 1)
= B(0, B(1, 0))
= B(0, B(0, 1))
= B(0, A(1, 1))
= B(0, 3)
= A(3, 3)
= 61
g(2) =
B(2, 2)
= B(1, B(2, 1))
= B(1, B(1, B(2, 0)))
= B(1, B(1, B(1, 1)))
= B(1, B(1, 61))
= B(1, B(0, B(1, 60)))
このあたりで、すでに書き下すことが困難になってくる。
B(1, 1)
= 61
B(1, 2)
= A(61, 61)
B(1, 3)
= A(A(61, 61), A(61, 61))
という調子で関数が増えていくので、B(1,61) はとんでもない数。g(2)=B(1,B(1,61)) なので、
g(2) ですでにグラハム数を超えているように思う。
g(2) ですでグラハム数を超えてしまい、さらに g(x) は x が増えるにつれてものすごい勢いで増
えるので、g(61) の大きさは想像を絶する。Ｓ変換 2 回目にして、g(61) というとんでもない数
が得られることになる。
Ｓ変換の３回目は
B(0, n) = g(n)
B(m + 1, 0)
= B(m, 1)
B(m + 1, n + 1) = B(m, B(m + 1, n))
gg(x) = B(x, x)
第 4 章 多重帰納関数
42
としたときの gg(x) となるので、
gg(1) =
B(1, 1)
= B(0, B(1, 0))
= B(0, B(0, 1))
= B(0, g(1))
= B(0, 61) = g(61)
gg(2) =
B(2, 2)
= B(1, B(2, 1))
= B(1, B(1, B(2, 0)))
= B(1, B(1, B(1, 1)))
= B(1, g(61))
B(1, 1)
= g(61)
B(1, 2)
= g(g(61))
B(1, 3)
= g(g(g(61)))
つまり、gg(2) は 61 を g(x) に代入して…と g(61) 回繰り返した数。この調子で gg(3),gg(4)... と
増えていき、gg(g(61)) が S 変換を３回繰り返した数。
SS 変換２回目は、SS 変換１回によって得られた m,f(x),S に対して S f (m) とする、すなわち
S 変換（つまり最初の S 変換を４回繰り返す変換）を f(m) 回繰り返す。ここで、f(m) 回とは SS
変換１回、つまり S 変換４回によって得られる大きな数 m を、これまた S 変換４回によって得
られる増加率の大きな関数 f(x) に代入した数なので、とてつもなく大きな数。その数だけ、新
S 変換を繰り返す、ということ。
つまり、大きな数と関数から大きな数と関数を生み出し、その生み出された大きな数と関数
から大きな S 変換を生み出し、大きな S 変換がさらにとてつもなく大きな数と関数を生み出す、
とお互いがお互いを増幅させていく。
この計算に対して、巨大数探索スレッドでは以下の様な反応となりました。
380 名前：１３２人目の素数さん ：02/07/02 19:47
うぎゃーーーーーーーーーーーーーっ！
！
！
でっ、でけえ！
！
！
フィッシュ数は文句なし世界一、宇宙一の数だ！
！
！
！
！
！
グラハム数とフィッシュ数を比べると、グラハム数は限りなく０に近い
お疲れ様でした、
386 名前：１３２人目の素数さん ：02/07/02 20:25
4.5. ふぃっしゅ数バージョン 1
43
ていうか
現実にあるものを文字にするだけの数字とかより
フィッシュ数のこと考えろ！
もうすごいから。すごいしヤバイから。
388 名前：１３２人目の素数さん ：02/07/02 20:32
小・中学生の頃、講談社のブルーバックスの宇宙や物理の本で
全宇宙のニュートリノの数とか光子の数が 10＾88 とかいう数字を見て
ぶったまげてたのが、なんかカワイク思えるよ
単に「とても大きな数を定義した」という以上の何者でもないのですが、これがこのように感銘を呼ぶと
ころが巨大数の不思議な魅力です。
巨大数探索スレッドでは、このふぃっしゅ数を具体的に計算しようとして、それがいかに巨大な数になる
か、といったことで盛り上がりを見せます5 。それが、巨大数探求の道へのスタートでした。
Code Ass (@aycabta) 氏6 が、ふぃっしゅ数バージョン 1 の Ruby による計算プログラム7 を作成しまし
た。ふぃっしゅ数は大きすぎるので、メモリや時間の制限で実際には計算できませんが、プログラムを読む
ことで計算の手順を確認することができます。Code Ass 氏は、他にもアッカーマン関数8 と矢印表記9 と
チェーン表記10 の計算プログラムを作成しました。
ふぃっしゅ数 F1 の S 変換は、関数 f(x) に 2 重帰納の操作をして関数 g(x) を生成する操作です。F1 は、
関数に 2 重帰納の操作を数多く繰り返すことによって、より大きな関数を生成するしくみである、と表現
できます。したがって、2 重帰納を 2 回施した時点で、2 重帰納を 1 回に原始帰納を繰り返したグラハム数
と比べて比較にならないほど大きな関数が生成されることとなります。ただし、この議論は厳密ではありま
せん。なぜならば、2 重帰納の操作は何度繰り返しても 2 重帰納のままなので、2 重帰納の回数では生成さ
れる関数の大小を比較できないからです。ここでは、グラハム数生成に使われている操作も F1 の S 変換も
同等のアッカーマン的な 2 重帰納操作であるため、このような比較が可能となっています。
F1 の定義において、f(x) から g(x) を生成する S 変換の漸化式は、f (z) = Ax (z, z)、g(z) = Ax (z, z) とす
ると、3 変数アッカーマンの式と一致します。このことから、3 変数アッカーマンにおける 2 重帰納操作と
F1 の定義における 2 重帰納操作は、同じであることが分かります。F1 の定義において、[3,x+1] に S 変換
を i 回繰り返して得られた関数を Si (x) とすると、S 変換の式は
Si+1 (0, n) = Si (n, n)
Si (m + 1, 0) =
Si (m + 1, n + 1) =
5 2ch
Si (m, 1)
Si (m, Si (m + 1, n))
過去ログ - 695 氏の計算 http://www.geocities.co.jp/Technopolis/9946/log/ln024.html
@aycabta https://twitter.com/aycabta
7 GitHub - aycabta/fish-number https://github.com/aycabta/fish-number
8 GitHub - aycabta/ackermannr https://github.com/aycabta/ackermann
9 GitHub - aycabta/arrow-notation https://github.com/aycabta/arrow-notation
10 GitHub - aycabta/chained-arrow-notation https://github.com/aycabta/chained-arrow-notation
6 Twitter
第 4 章 多重帰納関数
44
と書くことができ、3 変数アッカーマンの式と完全に一致します。したがって、F1 の S 変換 i 回後の計算に
おいて、B(m, n) = A(i, m.n) となります。S 変換を 1 回繰り返した後の g(2) がグラハム数を超えるという
計算は、A(1,2,2) がグラハム数よりも大きいことを計算したことになります。すなわち、
A(1, 1, 0)
= A(1, 0, 1) = A(1, 1) = 3
A(1, 1, 1)
= A(1, 0, 3) = A(3, 3) = 61
A(1, 1, 2)
= A(1, 0, 61) = A(61, 61) > 3 → 3 → 2 → 2 + 2
A(1, 1, 3) >
A(1, 0, f 2 (1) + 2) > 3 → 3 → 3 → 2 + 2
A(1, 1, x) > 3 → 3 → x → 2
A(1, 1, 65) > 3 → 3 → 65 → 2 > グラハム数
と、A(1,1,65) でグラハム数を超えます。
A(1, 2, 0)
= A(1, 1, 1) = 61
A(1, 2, 1)
= A(1, 1, 61) > 3 → 3 → 61 → 2
A(1, 2, 2) >
A(1, 1, 3 → 3 → 61 → 2) > 3 → 3 → (3 → 3 → 61 → 2) → 2
となるため、A(1,2,2) はグラハム数よりもはるかに大きな数です。
次に、F1 を 4 変数アッカーマン関数と比較します。まずは、4 変数アッカーマンを小さい方から順番に
計算してみます。
A(1, 0, 1, 0)
= A(1, 0, 0, 1) = A(1, 0, 1) = A(1, 1) = 3
A(1, 0, 1, 1)
= A(1, 0, 0, (A(1, 0, 1, 0))
= A(1, 0, 0, 3) = A(3, 0, 3) = A(2, 3, 3)
よって、A(1,0,1,1) は 2 重帰納です。
A(1, 0, 1, 2)
= A(1, 0, 0, A(1, 0, 1, 1))
= A(1, 0, 0, A(2, 3, 3))
= (A(2, 3, 3), 0, (2, 3, 3))
A(1, 0, 1, 3)
= A(1, 0, 0, A(1, 0, 1, 2))
= A(A(1, 0, 1, 2), 0, A(1, 0, 1, 2))
A(1, 0, 1, n + 1)
= A(1, 0, 0, A(1, 0, 1, n))
= A(A(1, 0, 1, n), 0, A(1, 0, 1, n))
A(1,0,1,2) は、2 重帰納を A(2,3,3) 回繰り返した数です。F1 の定義では、SS 変換が S 変換で生じた 2 重帰
納の数の回数だけ 2 重帰納を繰り返しているので、これに相当します。モーザー数では、原始帰納を原始帰
納の回数 (メガ回）繰り返すことで 2 重帰納の数ができました。それと同じことで、2 重帰納を 2 重帰納の
回数繰り返しているので、ここから 3 重帰納に入ると考えます。
4.6. ふぃっしゅ数バージョン 2
45
SS 変換の回数を重ねるごとに、その回数だけ S 変換を繰り返すので、SS 変換は A(1,0,1,n) の n を 1 増
やすことに相当します。実際には、SS 変換の指数部が m ではなくて f(m) になっているので、もっと複雑
に見えますが、m から f(m) へと増やすことは原始帰納なので、2 重帰納から見ると無視できる範囲です。
SS 変換の 1 回目は S 変換 4 回なので、2 重帰納を 2 回繰り返している A(1,0,1,1) よりは大きく、その回
数以上 S 変換を繰り返した SS 変換の 2 回目は、A(1,0,1,2) よりは大きく、…といったことで、SS 変換を
63 回繰り返した F1 は、A(1,0,1,63) よりは大きいと分かります。
さらに計算を続けます。
A(1, 0, 2, 0)
= A(1, 0, 1, 1) = A(2, 3, 3)
A(1, 0, 2, 1)
= A(1, 0, 1, (A(1, 0, 2, 0)))
= A(1, 0, 1, (A(2, 3, 3)))
A(1,0,2,1) は、S 変換を繰り返す SS 変換を A(2,3,3) 繰り返した数です。これは、F1 を超えています。SSS
変換を定義すれば A(1,0,2,1) になり、SSSS 変換は A(1,0,3,1) になり…といった感じになることでしょう。
さらに大きい A(1,1,1,1) を計算してみます。
A(1, 1, 1, 1) =
A(1, 1, 0, A(1, 1, 1, 0))
=
A(1, 1, 0, A(1, 1, 0, 1))
=
A(1, 1, 0, A(1, 0, 1, 1))
=
A(1, 1, 0, A(2, 3, 3))
=
A(1, 0, A(2, 3, 3), A(2, 3, 3))
これは、SSSS…と、S の文字数を A(2,3,3) 回繰り返した変換によって作られる数なので、F1 の定義をい
くら拡張しても追いつかない数です。
以上の計算から、
A(1, 0, 1, 63) < F1 < A(1, 0, 2, 1) < A(1, 1, 1, 1)
が F1 の大きさになります。
4.6
ふぃっしゅ数バージョン 2
ふぃっしゅ数バージョン 2 は以下の様に定義されます。
第 4 章 多重帰納関数
46
【定義】ふぃっしゅ数バージョン 2
[1] 自然数と関数のペアから、自然数と関数のペアへの写像 S（S 変換）を以下で定義する。
S : [m, f (x)] → [g(m), g(x)]
ただし g(x) は以下で与えられる。
B(0, n)
= f (n)
B(m + 1, 0) = B(m, 1)
B(m + 1, n + 1)
= B(m, B(m + 1, n))
g(x)
= B(x, x)
[2] 自然数、関数、Ｓ変換から同様の組を生み出す写像 SS を以下で定義する。
SS : [m, f (x), S] → [n, g(x), S2]
ただし S2 と n, g(x) は順次以下で与えられる。
S2
=
S2 : [m, f (x)] →
x
S2 : [m, f (x)] →
S f (m)
[n, p(x)]
[q(x), g(x)]
[3] [3,x+1,S] に SS 変換を 63 回繰り返して得た自然数を F2 、関数を F2 (x) とする。
F2 の定義は F1 と似ていますが、SS 変換の定義が変わっています。どこが変わっているかというと、
1. F1 の SS 変換で生成される関数は、2 重帰納である S 変換を一定回数繰り返す関数なので 2 重帰納関
数である。
2. F2 の SS 変換で生成される関数は、2 重帰納である S 変換の回数を数え上げる関数なので 3 重帰納関
数である。
ということです。どのようにして S 変換を数え上げているのかというと、
S2x : [m, f (x)] → [q(x), g(x)]
この式における、f(x) と g(x) の関係です。この式において、S 変換を f(x) 回繰り返した S2 変換を使ってい
ることは、関数を大きくする事に本質的に役立っていないので、
S x : [m, f (x)] → [q(x), g(x)]
としても同じ事です。この式で生成される g(x) がどんな関数かというと (S 変換における関数の変化に着目
します)、
g(1) は f(x) に S 変換を 1 回施して得られる g1 (x) に 1 を代入した g1 (1)
g(2) は f(x) に S 変換を 2 回施して得られる g2 (x) に 2 を代入した g2 (2)
4.7. 矢印回転表記とバード数
47
g(3) は f(x) に S 変換を 3 回施して得られる g3 (x) に 3 を代入した g3 (3)
g(n) は f(x) に S 変換を n 回施して得られる gn (x) に n を代入した gn (n)
というような関数 g(x) です。この関数 g(x) は、関数 f(x) に S 変換を有限回 (N 回) 施したいかなる関数
よりも、x > N において大きくなります。これが、つまり 2 重帰納である S 変換の操作を数え上げること
によって、いかなる 2 重帰納よりも強い 3 重帰納の操作とした S x (あるいは S2x ) を、SS 変換として定義
した、ということです。F2 (x) は、3 重帰納操作を 63 回施した 3 重帰納関数です。したがって、3 重帰納操
作を 1 回だけ含む A(1, 1, 1, 1) よりは大きい関数です。
F2 の計算は難しいのですが、次の F3 では F2 の S 変換が s(2) に、SS 変換が s(3) に相当します。F3 の
定義の方がすっきりしているので、そちらで理解する方が良いと思います。F2 は、F3 が生み出される前の
あまり洗練されていない定義です。
4.7
矢印回転表記とバード数
バード氏が考えた バードの矢印回転表記 (Bird’s revolving arrow notation) と バード数 (Bird’s number)
について、巨大数探索スレッドでは色々と議論がされてきました。このバード氏のホームページは、ug-
lypc.ggh.org.uk 上で公開されていましたが、消えてしまいました。巨大数探索スレッド 5 の発言 7
バードの矢印回転表記について、以下のように記録されています。
【定義】バードの矢印回転表記
11
には、
多変数関数↑ 1 を次で定める。
↑ 1(a)
↑ 1(a, b)
:= a
:= ab
↑ 1(a, b, ..., x, y, z)
:= ↑ 1(a, b, ..., x, y)(y = 1orz = 1)
↑ 1(a, b, ..., x, y, z)
:= ↑ 1(a, b, ..., x, ↑ 1(a, b, ..., x, y − 1, z), z − 1)(y > 1, z > 1)
多変数関数↑ n-1 から、多変数関数↑ n を作る (n > 1)。
↑ n(a)
↑ n(a, b)
:= a
:= ab
↑ n(a, b, c)
:= ab (b = 1orc = 1)
↑ n(a, b, 2)
:= ↑ n − 1(a, a, ..., a)(a が b 個)
↑ n(a, b, c)
:= ↑ n(a, ↑ n(a, b − 1, c), c − 1)(b > 1, c > 2)
↑ n(a, b, ..., x, y, z)
:= ↑ n(a, b, ..., x, y)(y = 1 or z = 1)
↑ n(a, b, ..., x, y, z) := ↑ n(a, b, ..., x, ↑ n(a, b, ..., x, y − 1, z), z − 1)(y > 1, z > 1)
ここで、↑ n(a, b, 2) の式を間違いやすいので、注意が必要です。そこだけ規則性が崩れています。チェー
ンとの対応は (a → b →... → x → y → z)=↑ 1(a,b,...,x,y,z) 、タワーとの対応は (a ↑...c 個... ↑ b)=(a → b
→ c)=↑ 1(a,b,c) となります。なお、この定義はオリジナルの表記を分かりやすい表記に書き直していま
11 2ch
過去ログ - 巨大数探索スレッド５ (1-530) http://www.geocities.co.jp/Technopolis/9946/log/ln051.html
第 4 章 多重帰納関数
48
す。オリジナルの表記と、上記定義との対応を示します。
a → b →...→ x → y → z
= ↑ 1(a, b, ..., x, y, z)
a ↓ b ↓...↓ x ↓ y ↓ z
= ↑ 2(a, b, ..., x, y, z)
a ← b ←...← x ← y ← z
= ↑ 3(a, b, ..., x, y, z)
このように、タワー表記の↑、チェーン表記の→を、さらに回転させていくことから矢印回転表記と呼ば
れます。この後、さらにチェーンを回転させると、タワー表記と区別できなくなるため、1 回転した時点で
(↑ 1) のように表記して、
a(↑ 1)b(↑ 1)...(↑ 1)x(↑ 1)y(↑ 1)z
a(↑ n)b(↑ n)...(↑ n)x(↑ n)y(↑ n)z
= ↑ 4(a, b, ..., x, y, z)
= ↑ 4n(a, b, ..., x, y, z)
となります。さらに、タワー表記のように回転矢印を重ねることもできます。
a(↑ n)[c]b = a(↑ n)(↑ n)...c 個...(↑ n)b
= a(↑ n)[c − 1][a(↑ n)[c]b − 1)]
c > 2 の定義は↑ [n+1](a,b,c) に吸収されるため、上記定義の中では c = 2 の定義式のみが記されています。
バード数は矢印回転表記をもとに、Bird 氏が作った巨大数ですが、これもオリジナルのホームページが
消えています。巨大数探索スレッドには、以下の様に記録されています。
まずは N ＝ 3(↑ G)[4]3 (G はグラハム数) というものを考えます。
(↑ G) とは G 回回転したチェーンのことで、これはタワーと同じように演算子として用います。
（チェーンの回転については省略）
(↑ G)[4] ＝ (↑ G)(↑ G)(↑ G)(↑ G) です。
すなわち N ＝ 3(↑ G)(↑ G)(↑ G)(↑ G)3 です。この N を下敷きにして、
X(1) ＝ N(↑ N)[N]N を考えます。そしてこれから
X(N) ＝ X(N-1)(↑ X(N-1))[X(N-1)]X(N-1) とパワーアップさせて、
この X(N) を X1 (N ) と呼び直します。(ここ不正確かも)
そんで、
X2 (1) ＝
X1 (N )
X2 (2) ＝
(X1 )2 (N ) ＝ X1 (X1 (N ))
X3 (1) ＝
X2 (N ) ＝ X1 N (N )
… とビシビシ強化して、(この辺の詳細も省略)
H ＝ XN (N ) を考えます。ここからまた XH (N ), (X(XH (N )) )(N ),…のように X の添字部分に
入れ子を作っていきます。
入れ子操作を XH (N ) 回行った結果生まれる巨大数が「ばーど数」です。多分。
非常に複雑な定義ですが、Xm (n) を X[m](n) と書き直すことで、この定義は以下の様に書く事ができ
ます。
4.7. 矢印回転表記とバード数
49
【定義】バード数（古い定義）
X[0](n) = ↑ n(n, n, n)
X[m + 1](n)
N
f (n)
としたとき、バード数 B = f f
2
(N )+1
= X[m]n (n)
= ↑ G(3, 3, 4)
= X[n](N )
(N )
ここで、H = f (n), XH (N ) = f 2 (N ) と計算されます。また、入れ子操作 n 回は f n+1 (N ) です。
なお、バード氏のホームページはその後 Large Numbers のサイトを管理している Robert Munafo 氏の
サーバー12 上で復活することになりますが、そこではまったく異なる新しいバード数の議論が展開されて
います。巨大数探索スレッドで当初議論されていたのは、バード氏の古い定義によるものなので、5 章まで
は古いバード数について書き、6 章以降では新しいバード数について書きます。
バードの回転矢印表記は、チェーン表記を元としているため、回転矢印の長さを 1 つ延ばす操作、すな
わち変数を 1 つ増やす操作が、2 重帰納操作です。したがって、変数の長さを数え上げる操作は 3 重帰納操
作です。↑ n(a, b, 2) の定義式は、↑ n − 1 の変数の長さを数え上げているので、↑ n − 1 から↑ n を作る
操作は 3 重帰納です。したがって、↑ n の n を変数として矢印の回転数を数え上げると、4 重帰納関数がで
きます。
バード数の定義は、X[m](n) の定義において、4 重帰納の矢印回転関数を n 回繰り返す操作を m 回繰り返
しているので、4 重帰納に 2 重帰納を加えています。さらに、バード数の生成では合成が加わっています。
4 重帰納、2 重帰納、原始帰納、合成を組み合わせた 4 重帰納です。
チェーン、バードの矢印回転関数、ふぃっしゅ数の比較については、巨大数探索スレッドで白熱した議論
がされましたが、以上から、
1. 2 重帰納: チェーンを伸ばす操作、F1 (x)
2. 3 重帰納: 矢印を回転させる操作、F2 (x)
3. 4 重帰納: 矢印回転関数、バード数
となります。
続いて、バード数と多変数アッカーマン関数を比較します。
g(n) = X[n](n) とすると、g(2) > N より、g n+1 (2) > f n (N ) となります。したがって、
B = ff
2
(N )+1
(N ) < g g
3
(2)+2
(2)
となります。 ここで、X[m](n) < A(1, 0, 0, m, n) であることが、
X[0](n) = ↑ n(n, n, n)
X[m + 1](n) = X[m]n (n)
12 Robert
Munafo http://mrob.com/
第 4 章 多重帰納関数
50
この漸化式と、
A(1, 0, 0, 0, n) =
A(1, 0, 0, m + 1, n) =
A(n, 0, 0, n) ≒↑ n(n, n, n) = X[0]n
A[m]n (A(1, 0, 0, m + 1, 0))(A[m](x) = A(1, 0, 0, m, x))
この漸化式から分かります。したがって、
g(n) = X[n](n) < A(1, 0, 0, n, n) < A(1, 0, 1, 0, 2n)
となります。この式は、すなわち関数 g(n) = X[n](n) が、4 重帰納 1 回 (矢印回転関数) と 2 重帰納 1 回 (n
重の入れ子操作) から計算されるところから、導かれた式です。
バード数は g(n) から原始帰納的に導かれるため、計算を単純化することで以下のように A(1,0,1,1,*) の
形にすることができます。g n (2) < A(1, 0, 1, 1, 2n) より、
B
= gg
3
(2)+2
(2)
< A(1, 0, 1, 1, A(1, 0, 1, 1, 6) ∗ 2 + 4)
< A(1, 0, 1, 1, A(1, 0, 1, 1, A(1, 0, 1, 2, 0)))
= A(1, 0, 1, 2, 2)
すなわち、B < A(1, 0, 1, 2, 2) となります。
したがって、たとえば A(1,1,1,1,1) は、バード数よりもはるかに大きくなります。
A(1, 1, 1, 1, 1) =
A(1, 1, 1, 0, A(1, 1, 1, 1, 0))
= A(1, 1, 1, 0, A(1, 1, 0, 1, 1))
= A(1, 1, 1, 0, A(1, 1, 0, 0, A(1, 0, 0, 1, 1)))
= A(1, 1, 1, 0, A(1, 1, 0, 0, A(1, 0, 0, 0, 3)))
= A(1, 1, 1, 0, A(1, 1, 0, 0, A(2, 2, 3, 3)))
= A(1, 1, 1, 0, A(1, 0, A(2, 2, 3, 3), 0, A(2, 2, 3, 3)))
> A(1, 1, 1, 0, A(1, 0, 2, 1, 2))
> A(1, 1, 1, 0, B)
4.8
ふぃっしゅ数バージョン 3
ふぃっしゅ数バージョン 3 (F3 ) は、以下のように定義されます。
4.8. ふぃっしゅ数バージョン 3
51
【定義】ふぃっしゅ数バージョン 3
[1] 関数 f(x) から g(x) への写像 s(n) (n > 0) を以下のように定める。
s(1)f
:= g; g(x) = f x (x)[原始帰納]
s(n)f
:= g; g(x) = [s(n − 1)x ]f (x)(n > 1)[n 重帰納]
[2] 関数 f(x) から g(x) への写像 ss(n) (n > 0) を以下のように定める。
ss(1)f
:= g; g(x) = s(x)f (x)[帰納回数の数え上げ]
ss(n)f
:= g; g(x) = [ss(n − 1)x ]f (x)(n > 1)[さらに数え上げ]
[3] ふぃっしゅ関数 F3 (x) を以下のように定める。
F3 (x) := ss(2)63 f ; f (x) = x + 1
[4] ふぃっしゅ数 F3 := F363 (3) とする。
この定義は、F1 や F2 と比べると異なった表現が用いられていますが、内容は F2 の拡張です。また、
「巨
大数探索スレッド」で定義された F3 (旧 F3 ) の定義とも、異なっています。旧 F3 の定義の中で、最も本質
的な部分を記述したものが新 F3 です。旧 F3 の定義については、煩雑になるためここには記しません。
そこで、F1 ,F2 , 旧 F3 , 新 F3 の定義の変遷についてまとめます。
表 4.1: F1 から F3 までの定義の変遷
バージョン
定義
F1
2 重帰納操作である S 変換 (数と関数のペアから数と関数のペアへの写像)
S 変換を多数回繰り返す操作 (SS 変換)
F2
S 変換 (2 重帰納) の回数を数え上げる SS 変換 (3 重帰納)
(SS 変換は数、関数、S 変換から数、関数、S 変換への写像)
旧 F3
F2 の S 変換,SS 変換,SSS... 変換の定義に相当する s(n) 変換 (多重帰納)
帰納回数を数え上げる ss(1) 変換
新 F3
F3 の s(n) 変換の定義を、関数から関数への写像（汎関数）へと簡略化
s(1) 変換の定義 (F1 ,F2 の S 変換に相当) を、2 重帰納から原始帰納へと簡略化
つまり、F1 から旧 F3 まで、定義を拡張することでより高い帰納程度を持つ関数、そして巨大数を作って
きましたが、その結果、旧 F3 の定義は非常に複雑なものになりました。新 F3 では、旧 F3 の定義の中か
ら、高い帰納程度を持つ関数を作るために必要な定義のみを残して簡略化しました。旧 F3 と新 F3 の大き
さは厳密には異なりますが、関数の帰納程度が同程度になります。
ここで、新 F3 の定義の 2 つの簡略化について説明します。まずは、1 つ目の簡略化についてです。SS 変
換は「数と関数と S 変換」から「数と関数と S 変換」への写像であり、S 変換の回数を数え上げることで、
大きな関数を作っています。S 変換そのものは、S 変換の回数を増やすことで大きくしていますが、そのこ
第 4 章 多重帰納関数
52
と自体は関数の大きさを大きくする事に本質的に役立っていません。したがって、SS 変換の定義の中で、
S 変換を大きくするしくみは「無駄なしくみ」ということになります。また、数を関数に代入する定義につ
いても、関数さえ定義されれば最終的にできた関数に数を代入すればいいのですから、「無駄な定義」とい
うことになります。このように、SS 変換の定義は「関数から関数への写像」つまり汎関数の定義の部分が
本質的ということになります。そこで、s(n) 変換は汎関数を定義としました。
次に、新 F3 の 2 つ目の簡略化について説明します。これまで、S 変換はアッカーマンを元にした 2 重帰
納操作で定義されていました。そして、2 重帰納操作を数え上げることで 3 重帰納操作を、それをまた数え
上げることで 4 重帰納操作を、という定義を重ねる事で、多重帰納操作が定義されました。ここで、2 重帰
納操作そのものは、原始帰納操作の数え上げで定義できますから、元となる操作は 2 重帰納である必要は
なく、原始帰納で十分ということになります。そうすれば、原始帰納の数え上げから 2 重帰納、その数え上
げから 3 重帰納と、多重帰納を定義できます。そこで、新 F3 の s(1) は原始帰納定義としました。新 F3 の
s(2)、すなわち
s(1)f
:= g; g(x) = f x (x)
s(2)f
:= g; g(x) = [s(1)x ]f (x)
から計算される s(2) は、F1 や F2 の S 変換とは異なりますが、同じ程度の大きさの 2 重帰納操作となりま
す。s(1)f := g; g(x) = f x+1 (1) とすれば、s(2) は F1 や F2 の S 変換と一致します。
F3 の s(n) と多変数アッカーマン関数の大きさは、以下の様に比較できます。
f (x) = x + 1 とすると
[s(1)a1 ][s(2)a2 ]...[s(n)an ]f (x) ≈ A(an , ...a2 , a1 , x)
ここで、s(1) の定義として s(1)f := g; g(x) = f x+1 (1) を採用すると両辺がイコールになります。このこと
は、F3 の s(n) と多変数アッカーマン関数の漸化式を比較すると両者が一致することで示す事ができます。
つまり、多重帰納の計算手順を定義したものが多変数アッカーマン関数、多重帰納における「操作の数え
上げ」を汎関数で表現したものが F3 の s(n) であり、両者は等価である、ということになります。
ss(1) は、g(x) = s(x)f (x) によって関数 f(x) に対する x 重帰納を定義しています。これは多重帰納の回
数を数え上げるもので、f(x)=x+1 としてこのように計算されます。
ss(1)f (1)
=
s(1)f (1) ≈ A(1, 1)
ss(1)f (2)
=
s(2)f (2) ≈ A(1, 0, 2)
ss(1)f (3)
=
s(3)f (3) ≈ A(1, 0, 0, 3)
ss(1)f (4)
=
s(4)f (4) ≈ A(1, 0, 0, 0, 4)
ss(1)f (5)
=
s(5)f (5) ≈ A(1, 0, 0, 0, 0, 5)
…
ss(1)f (n)
=
s(n)f (n) ≈ A(1, (0 が n − 1 個), n)
ss(1) によって生成される x 重帰納関数 ss(1)f(x)=s(x)f(x) は、どのような多重帰納関数よりも大きな関数
です。ある i 重帰納関数 gi (x) を考えた時に、x > i において常に s(x)f (x) > gi (x) となるためです。つま
り、ss(1)f(x) は多重帰納以上の関数であるということです。
F3 (x) は、この ss(1) という操作の数え上げ操作を 63 回繰り返したものです。このように、F3 (x) は多重
帰納関数よりも大きな関数です。
4.9. ここまでに出てきた巨大数の比較
53
表 4.2: 巨大数の大小比較 (下の数ほど大きい)
巨大数
帰納の程度
68
無量大数 = 10
原始帰納
グーゴル = 10 ↑ 10 ↑ 2
不可説不可説転 = 10 ↑ (7 × 2
4.9
原始帰納
122
)
原始帰納
グーゴルプレックス = 10 ↑ 10 ↑ 10 ↑ 2
原始帰納
第 2 スキューズ数 ≈ 10 ↑ 10 ↑ 10 ↑ 10 ↑ 3
原始帰納
トリトリ = 3 ↑↑↑ 3 = 3 → 3 → 3
原始帰納
モーザー数
3→3→3→2
G: グラハム数
2 重帰納
2 重帰納
2 重帰納
3→3→3→3
A(3,3,3)
2 重帰納
2 重帰納
3 →...(G 個)... → 3
A(1,0,1,63)
F1 : ふぃっしゅ数 V1
2 重帰納
3 重帰納
3 重帰納
A(1,0,2,1)
A(1,1,1,1)
3 重帰納
3 重帰納
↑ 3(3,3,3) = 3 ← 3 ← 3
F2 : ふぃっしゅ数 V2
↑ G(3,3,3) = 3 ← 3 ← 3
3 重帰納
3 重帰納
3 重帰納
B: バード数 (古い定義)
A(1,1,1,1,1)
4 重帰納
4 重帰納
A(1,...(B 個)...,1)
F3 : ふぃっしゅ数 V3
(B-1) 重帰納
多重帰納以上
ここまでに出てきた巨大数の比較
本書は「巨大関数論」ではなくて「巨大数論」としていますが、ここまでは帰納関数の定義について議
論が集中していました。そこで、これまでに登場した巨大数の大きさを比較します。表 4.2 は、ここまでに
出てきた巨大数を一覧にしています。巨大数生成に使われる関数がどの程度の帰納関数であるかを「帰納の
程度」として表しています。
54
第 5 章 順序数とハーディー関数
5.1
多重帰納を超えて
前章で示したように、F3 (x) はいかなる多重帰納関数よりも大きな関数です。ここから先は、F3 (x) より
も大きな関数、そして巨大数を探求する事になります。では、そのように大きな関数を、どうやって比較す
るのでしょうか。
本書に登場する大きな関数は、計算によって値を求めることで大きさを比較することは現実的に不可能
です。グラハム数ですら実際に計算することは無理ですから、それよりも大きな巨大数については関数の性
質を調べて大きさを比較するよりありません。
多重帰納の範囲にある関数であれば、たとえば、3 重帰納関数の F2 (x) よりも、4 重帰納関数の矢印回転
関数の方が大きい、というように、それが何重帰納であるかを調べる事で、関数の大きさを比較できます。
では、多重帰納よりも大きな関数を定義したときに、その大きさをどのように比較するのでしょうか。
そのための有効な手段が、本章で解説するハーディー関数です。ハーディー関数を理解するためには、ま
ず「順序数」の理解が必要です。ハーディー関数は、関数の大きさを順序数によって階層づけることができ
ます。多重関数以上の関数についても、その大きさを相当する Hardy 関数によって対応づけられる順序数
の大きさによって比較する事が可能となります。
そこで、本章ではまず順序数とハーディー関数について解説し、これまでに出てきた関数の大きさをハー
ディー関数を用いて評価します。次章以降では、様々な関数の大きさを主としてハーディー関数 H[α](x) ま
たは F[α](x) を用いて評価します。
5.2
順序数
Wikipedia には、 順序数 (Ordinal number)
1
について以下のように定義されています（2007 年の記述）。
【定義】順序数
順序数（じゅんじょすう）とは、順序構造すなわち集合の元（要素、element）の間の序列のつけ方 を
あらわす順序型の特別なもののことである。
n 個の元からなる有限集合の順序数は、自然数の集合 1,2, ..., n に通常の大小関係で序列をつけたもの
であり、これを集合の元の数と同じ文字 n で表す。このように自然数の n と順序数の n はまったく別
のもの であるが、（後に定める順序数の演算とともに）これを同一視して順序数は自然数の拡張 （の
一つ）であると見なす。
順序数には、 有限順序数 と 無限順序数 (超限順序数) の 2 種類があります。ここでは、自然数は有限順序
数です。自然数以外の順序数は無限順序数です。無限順序数の中で最小のものをωと呼びます。そうすると、数
1 Wikipedia
- 順序数 http://bit.ly/GTUIjU (ja.wikipedia.org)
5.2. 順序数
55
列 1,2,3,4,5,…はωに収束します。このとき、1,2,3,4,5,…を、ωに収束する 基本列 (fundamental sequence)
あるいは 収束列 と呼びます。ωに対する収束列は、1 種類とは限りません。たとえば、数列 2,4,6,... もω
への収束列となります。
最小の無限順序数ωに対して、ω+1, ω+2,.. といった順序数を定義することができます。なお、順序数では交
換法則が成り立ちません。1+ωは 1+1,1+2,1+3,... と計算したときの極限なので、1+ω=ωとなります。ここ
で、αが順序数のとき、ある順序数βが存在してα=β+1 となるならば、αは 後続順序数 (successor ordinal)
であると言います。後続順序数でない順序数は 極限順序数 (limit ordinal) と呼びます。ωは極限順序数で、
ω+a(a=1,2,3,...) は後続順序数です。すべての順序数は、0 または後続順序数または極限順序数です。極限
順序数は、基本列によって定義できるものと、基本列が存在しないものがあります。
極限順序数は、次のように定義することもできます。
αよりも小さいすべての順序数ζに対して、ζ < ξ < α となる順序数ξが存在するとき、αは極限
順序数である。
たとえば、0, 1, 2, …, ω, ω + 1 という数列を考えると、α = ω + 1 に対しては ζ = ω とすると ω < ξ <
ω + 1 となる ξ が存在しないので、ω + 1 は極限順序数の定義には合致しませんが、α = ω に対しては、
αよりも小さい順序数ζ（つまり自然数）を取ると、ξ = ζ + 1 が必ず存在するため、極限順序数の定義
に合致します。
ω + 1, ω + 2, … という基本列を考えると、この数列は ω + ω に収束します。したがって、ω + ω は極
限順序数です。この時に、ω + ω のことを ω× 2 と書きます。ここでも、順序数に関しては通常の交換法
則が成り立たず、2 ×ω = ω となりますので（2+2+…と計算していった時の極限は、1+1+…と計算する
ことの極限と同じ)、2 ω ではなく ω× 2 と表記する必要があります。
極限順序数ω× 2 に対して、後続順序数ω× 2+a (a=1,2,3,...) を定義できます。そして、ω× 3 はω×
2+1, ω× 2+2,... を基本列とする極限順序数です。このように、後続順序数の定義 (+1) と極限順序数の定
義を繰り返す事で、順序数が定義されます。基本列 a1, a2, a3, … の極限順序数αを α = lim(a1, a2, a3, ...)
と表記することにすると、以下のように順序数が定義されます。
ω× 3
=
lim(ω× 2, ω× 2 + 1, ω× 2 + 2, ...)
ω× 4
=
lim(ω× 3, ω× 3 + 1, ω× 3 + 2, ...)
ω× a
= lim(ω× (a − 1), ω× (a − 1) + 1, ω× (a − 1) + 2, ...)
このように、極限順序数ω× a は、ω× (a-1) から後続順序数を順番に計算する基本列を取れば、定義出来
ます。続いて、このように定義されたω× a を使って、
ω2
:= ω×ω = lim(ω, ω× 2, ω× 3, ...)
といった基本列を取る事により、ω2 という順序数を定義出来ます。これよりも大きな順序数については、
これまでと同じような基本列の取り方で、以下のように極限順序数の定義を続けることができます。
ω2 + ω
ω2 + ω× a
= lim(ω2 , ω2 + 1, ω2 + 2, ...)
= lim(ω2 + ω× (a − 1), ω2 + ω× (a − 1) + 1, ω2 + ω× (a − 1) + 2, ...)
第 5 章 順序数とハーディー関数
56
ω2 × 2
=
ω2 + ω2 = lim(ω2 , ω2 + ω, ω2 + ω× 2, ...)
ω3
= ω2 ×ω = lim(ω2 , ω2 × 2, ω2 × 3, ...)
ωω
= lim(ω, ω2 , ω3 , ω4 , ...)
ωω × 2
=
ωω + ωω = lim(ωω , ωω + ω2 , ωω + ω3 , ...)
ωω+1
= ωω ×ω = lim(ωω , ωω × 2, ωω × 3, ...)
ωω+2
= ωω+1 ×ω = lim(ωω+1 , ωω+1 × 2, ωω+1 × 3, ...)
ωω× 2
= ωω×ω = lim(ωω , ωω× 2 , ωω× 3 , ...)
ω
= lim(ωω , ωω , ωω , ...)
ωω
ωω
ω
ωω + ω
ω
= ωω+ω = lim(ωω , ωω+1 , ωω+2 , ...)
2
ωω + ω× 2
2
ω
3
ω
ω
= lim(ωω , ωω + 1, ωω + 2, ...)
=
ω
ω
ω
lim(ωω + ω, ωω + ω + 1, ωω + ω + 2, ...)
ω
また、それぞれの極限順序数に自然数を加えた順序数、たとえば ωω + 3 は、後続順序数になります。
ω
ここまでで、ω、ωω 、ωω を定義することができました。ここで、ω∧∧ a := ω∧ ω∧ ω∧ ...ω (a 個の
ω) と表記することにすると、同様の定義を繰り返せば、
ω, ωω , ω∧∧ 3, ω∧∧ 4, ω∧∧ 5, ...
を、順次定義出来ます。そこで、これを基本列として、極限順序数 ε0 （エプシロン・ノート）2 を
ε0 = lim(ω, ωω , ω∧∧ 3, ω∧∧ 4, ω∧∧ 5, ...)
と定義します。
5.3
カントールの標準形
ε0 よりも小さな全ての順序数は、 カントールの標準形 (Cantor normal form)
3 4
(しばしば CNF と略
される) で一意に書く事ができます。
【定義】カントールの標準形
正の整数 c1 , c2 , c3 , · · · , ck と順序数 β1 > β2 > · · · > βk ≥ 0 に対して、順序数 α < ε0 を
α
=
k
X
ωβi ci
i=1
= ωβ1 c1 + ωβ2 c2 + · · · + ωβk ck
の形で書く時、これをカントールの標準形と言う。
2 Wikipedia
- エプシロン・ノート http://bit.ly/16Is9QQ (ja.wikipedia.org)
- Cantor Normal Form http://www.proofwiki.org/wiki/Definition:Cantor Normal Form
4 Wikipedia - Ordinal arithmetic https://en.wikipedia.org/wiki/Ordinal arithmetic
3 ProofWiki
5.4. ハーディー関数
57
さて、1891 年にジュゼッペ・ペアノが自然数全体を公理化した ペアノの公理 (Peano axioms)
5
とい
う公理体系を作りました。その公理系は自然数を集合論で記述しています。この公理体系によって、加算、
乗算、冪乗のような演算が定義できて、これを ペアノ算術 (Peano arithmetic) と言います。このペアノ算
術で、先ほどの計算のように、ωから有限回の加算・乗算・冪状で到達できるような ε0 よりも小さい順序
数、すなわちカントール標準形で書ける順序数が定義出来ます。
冪乗の冪乗の…という極限から、先ほどのように ε0 を定義できますが、これはペアノ算術から導かれる
計算とは異なり、超限帰納 (transfinite induction) と呼ばれます。ε0 は、ωから有限回の加算・乗算・冪
状では到達できない最小の順序数です。
5.4
ハーディー関数
ハーディー関数 (Hardy function) は、以下の様に定義されます。
【定義】ハーディー関数
H[0](x) =
H[α + 1](x) =
H[α](x) =
x
H[α](x + 1)
H[αx ](x)(αが極限順序数の時)
順序数の定義の中で、後続順序数の定義 (順序数に+1 する) と、基本列の極限による極限順序数の定義
を、それぞれ関数に x+1 を代入する操作と、対角化の操作に対応させることにより、関数の階層性を順序
数の階層性と対応づけています。
ここで、定義の中に基本列が用いられていますが、基本列の取り方は一様ではないため、αの定義にあら
われるすべての基本列の取り方を厳密に定めて、はじめて H[α] が定義されたことになります。ただし、基
本列のとり方による増大度の違いよりは、順序数の大きさによる増大度の方がはるかに大きい為、基本列
の取り方いかんに関わらず、α > β であれば H[α] > H[β] が成り立つため、H[順序数] と記述して大体
の大きさを表します。
また、基本列の中でなんらかの方法で 1 つの 正規な基本列 (canonical fundamental sequence) を与え、
H[αx ] の正規な基本列であるとすることで、H[α] の定義は一意に定まります。
f (x) = H[α](x) としたときに (f (x) = x + 1 のときに α = 1)
H[α × 2](x)
= f (f (x))(合成)
H[α × n](x)
= f n (x)(合成 n 回)
H[α × ω](x)
= f x (x)(原始帰納)
= ff
H[α × ω ω ](x)
:
f の 2 重帰納関数
H[α × ω
H[α × ω
5 Wikipedia
x
H[α × ω 2 ](x)
(x)
(f x (x))(原始帰納 2 回)
ω×2
](x)
:
2 重帰納 2 回
ω×n
](x)
:
2 重帰納 n 回
- Peano axioms https://en.wikipedia.org/wiki/Peano arithmetic
第 5 章 順序数とハーディー関数
58
2
H[α × ω ω ](x)
:
3 重帰納
](x)
:
3 重帰納 n 回
](x)
:
4 重帰納
H[α × ω ω ](x)
:
n + 1 重帰納
:
x 重帰納 (多重帰納以上)
H[α × ω ω
2
×n
H[α × ω
ω3
n
H[α × ω
ωω
](x)
また、以下のような F[α](x) を定義することにより、
【定義】ハーディー関数の別表記
F [0](x)
F [α + 1](x)
= x+1
= F [α]x (x)(αが後続順序数の時)
F [α](x) = F [αx ](x)(αが極限順序数の時)
f (x) = F [α](x) として (f (x) = x + 1 のときに α = 0)
F [α + 1](x)
= f x (x)(原始帰納)
F [α + ω](x)
:
2 重帰納
F [α + ω ](x)
:
3 重帰納
F [α + ω n ](x)
:
n + 1 重帰納
:
x 重帰納 (多重帰納以上)
2
ω
F [α + ω ](x)
といったように、
F [α](x) ≒ H[ωα ](x)
となり、表記が若干楽になります。これは、 急成長階層 (Fast-growing hierarchy) とも言われ、巨大数探
索スレッドでも使われ、Googology Wiki でも fα という表記で使われています6 。
5.5
色々な関数のハーディー関数による近似
F3 の計算: f (x) = F [α](x) として
ss(1)f (x)
≒
F [α + ωω ](x)
ss(1)2 f (x)
≒
F [α + ωω × 2](x)
ss(2)f (x)
=
ss(1)x f (x) ≒ F [α + ωω × ω](x) = F [α + ωω+1 ](x)
F3 (x)
=
ss(2)63 f (x) ≒ F [α + ωω+1 × 63](x)
なお、ここから先は
ss(3)f (x)
6 Fast-growing
=
ss(2)x f (x) ≒ F [α + ωω+2 ](x)
hierarchy http://googology.wikia.com/wiki/FGH
5.5. 色々な関数のハーディー関数による近似
59
ss(4)f (x)
=
ss(3)x f (x) ≒ F [α + ωω+3 ](x)
ss(x)f (x)
≒
F [α + ωω×2 ](x)
このように計算されます。
表 5.1: 色々な関数のハーディー関数による近似 (N は大きな整数)
関数
H[α] による近似
F[α] による近似
Knuth の上矢印 3(↑ n)3
A(n, 3)
F1 , F2 の S 変換 1 回
H[ωω ](n)
H[ωω ](n)
H[ωω ](n)
F [ω](n)
F [ω](n)
F [ω](n)
F1 (n)
n 個の n からなる Conway のチェーン
H[ωω×N ](n)
2
H[ωω ](n)
F [ω × N ](n)
F [ω2 ](n)
F3 の s(2)n 回≒ F1 , F2 の S 変換 n 回
F2 (n)
チェーンの回転↑ n(3, 3, 3)
H[ωω ](n)
2
H[ωω ×63 ](n)
3
H[ωω ](n)
F3 の s(3)n 回≒ F2 の SS 変換 n 回
バード数の X(n, 1, 1)
2
F [ω2 ](n)
F [ω2 × 63](n)
F [ω3 ](n)
H[ωω ](n)
3
H[ωω +ω+1 ](n)
3
F [ω3 ](n)
F [ω3 + ω + 1](n)
A(1, 0, 2, 1, n)
A(1, 0, 0, 0, 0, n) = A(n, 0, 0, 0, n)
A(n, n, n, n, n)
H[ωω +ω×2+1 ](n)
4
H[ωω ](n)
4
H[ωω ](n)
3
F [ω3 + ω × 2 + 1](n)
F [ω4 ](n)
F [ω4 ](n)
F3 の s(4)n 回
H[ωω ](n)
4
F [ω4 ](n)
ω
F [ωω ](n)
ω
F [ωω ](n)
A(n 個の n)orA(n 個の 1)
F3 の s(n)
F3 (n)
H[ωω ](n)
H[ωω ](n)
ωω+1 ×63
H[ω
](n)
F [ωω+1 × 63](n)
60
第 6 章 証明可能帰納関数
6.1
証明可能帰納関数
証明可能帰納関数 (provably recursive function) とは、ペアノ算術で証明可能な関数のことです。前章で
は、ωから有限回の加算、乗算、冪乗で到達出来ない順序数が ε0 であること、そして α < ε0 の時に、
順序数αが一意にカントール標準形で書けることを紹介しました。このような、カントール標準形で書く
事のできる順序数 α < ε0 に対して、ハーディー関数 H[α] および F [α] で与えられる関数は、証明可能
帰納関数となります。ハーディー関数は、ε0 に到達した時に H[ε0 ] = F [ε0 ] となりますが、H[ε0 ] は証
明可能帰納関数ではありません。本章では、H[ε0 ] も含めた H[ε0 ] 以下の関数について扱います。
6.2
2 重リストアッカーマン関数
たろう氏は、多変数アッカーマン関数を２重リストに拡張して、2 重リストアッカーマン関数を定義しま
した1 。多変数アッカーマンの n 個目の引数が a であることを、[n, a] と表現するようにし、[] の中を多変
ω
数化することで拡張しました。これは、F [ωω ](n) 程度の増大度の関数となります。
【定義】2 重リストアッカーマン関数
□ : 0 個以上の 0
Ｘ : 0 個以上の 0 以上の整数
Ｙ, Ｙ 1, Ｙ 2 : 0 個以上の 0 以上の整数リスト
a, b, c : 0 以上の整数
N : 十分大きな整数に対し、
index [..., b3, b2, b1, b0, a0] = ... + N 3 ・b3 + N 2 ・b2 + N・b1 + b0
とし、
Ak( ) の中のリストは index の大きい順に表記する。
また、index が同じとなるリストは Ak( ) 内に複数含まないとする。
Ak(Ｙ 1, [Ｘ, 0], Ｙ 2) = Ak(Ｙ 1, Ｙ 2)
Ak(Ｙ 1, [□, Ｘ], Ｙ 2) = Ak(Ｙ 1, [Ｘ], Ｙ 2)
Ak([a]) = a+1
Ak(Ｙ, [1, b+1]) = Ak(Ｙ, [1, b], [1])
Ak(Ｙ, [1, b+1], [a+1]) = Ak( Ｙ, [1, b], [Ak(Ｙ, [1, b+1], [a])] )
Ak(Ｙ, [Ｘ, c+1, b+1], [a]) = Ak(Ｙ, [Ｘ, c+1, b], [Ｘ, c, a], [a]) ... Ｘ ≠ □ or c ≠ 0
Ak(Ｙ, [Ｘ, c+1, 0, □, b+1], [a]) = Ak(Ｙ, [Ｘ, c+1, 0, □, b], [Ｘ, c, a, □, a], [a])
1 再掲：巨大数探索スレッド
7-571 でアップされた文書 (たろう, 2007 年 10 月 17 日) http://gyafun.jp/ln/archive/7-571.txt
6.3. ふぃっしゅ数バージョン 3 の拡張
61
以下のように計算されています。
Ak([n, 1], [n]) ≈ F [ωω ](n)
Ak([1, 0, 1], [n]) ≈ F [ωω ](n)
Ak([a, 0, 1], [n]) ≈ F [ω( ω・a)](n)
2
Ak([n, 0, 1], [n]) ≈ F [ωω ](n)
2
Ak([1, 0, 0, 1], [n]) ≈ F [ωω ](n)
2
Ak([a, 0, 0, 1], [n]) ≈ F [ωω ・a ](n)
3
Ak([n, 0, 0, 1], [n]) ≈ F [ωω ](n)
3
Ak([1, 0, 0, 0, 1], [n]) ≈ F [ωω ](n)
4
Ak([1, 0, 0, 0, 0, 1], [n]) ≈ F [ωω ](n)
5
Ak([1, 0, 0, 0, 0, 0, 1], [n]) ≈ F [ωω ](n)
Ak(..., [3, a3], [2, a2], [1, a1], [0, a0]) ≈ Ak(a3, a2, a1, a0)
3
2
Ak([..., b3, b2, b1, b0, a], [n]) ≈ F [ω...+ω ・b3+ω ・b2+ω・b1+b0・a](n)
ω
Ak([n 個の 1], [n]) ≈ F [ωω ](n)
6.3
ふぃっしゅ数バージョン 3 の拡張
前章で、F3 の定義において
ss(x)f (x) ≈ F [α + ωω×2 ](x)
と計算がされました。ここで、s(x) を 3 変数化して
s(1, 1, 1)
:= s(1)
s(a, 1, 1)f
:= g; g(x) = s(a − 1, x, x)f (x)(a > 1)
s(a, b, 1)f
:= g; g(x) = s(a, b − 1, x)f (x)(b > 1)
s(a, b, c)f
:= g; g(x) = [s(a, b, c − 1)x ]f (x)(c > 1)
とします。すなわち、s(1, 1, n) = s(n), s(1, 2, n) = ss(n) です。このように定義すると、以下のような計算
ができます。
s(1, 2, x)f (x) = ss(x)f (x) ≈ F [α + ωω×2 ](x)
s(1, 3, 1)f (x) = s(1, 2, x)f (x) ≈ F [α + ωω×2 ](x)
s(1, 3, 2)f (x) = s(1, 3, 1)x f (x) ≈ F [α + ωω×2+1 ](x)
s(1, 3, 3)f (x) = s(1, 3, 1)x f (x) ≈ F [α + ωω×2+2 ](x)
s(1, 3, x)f (x) ≈ F [α + ωω×3 ](x)
2
s(1, x, x)f (x) ≈ F [α + ωω ](x)
2
s(2, 1, 1)f (x) = s(1, x, x)f (x) ≈ F [α + ωω ](x)
s(2, 1, 2)f (x) ≈ F [α + ωω
2
+1
](x)
第 6 章 証明可能帰納関数
62
2
s(2, 2, 1)f (x) = s(2, 1, x)x f (x) ≈ F [α + ωω
s(2, 2, x)f (x) ≈ F [α + ωω
2
+ω× 2
](x)
ω +ω× 3
](x)
2
s(2, 3, x)f (x) ≈ F [α + ω
+ω
](x)
2
s(3, 1, 1)f (x) = s(2, x, x)f (x) = s(2, 2, x)x f (x) ≈ F [α + ωω
ω
s(x, 1, 1)f (x) ≈ F [α + ω
3
×2
](x)
(x)
3
このように、3 変数の s(x) 変換 s(x,x,x) の大きさが F [α + ωω ](x) 程度なので、x 変数の s(x) 変換 s(x,x,...(x
ω
個),...x) を考えると、その大きさは F [α + ωω ](x) 程度となります。
6.4
多重リストアッカーマン関数
たろう氏は、多変数アッカーマンから２重リストアッカーマンに拡張したのと同様の拡張を繰り返すこと
で、多重リストアッカーマンが定義できるとしました。その大きさは、以下のように計算されています2 。
多重リストアッカーマン関数の大きさ
3 重リスト
ω
Ak([[1, 0, 1], [1]], [[n]]) ≒ F [ωω ](n)
ω2
Ak([[1, 0, 0, 1], [1]], [[n]]) ≒ F [ωω ](n)
ω3
Ak([[1, 0, 0, 0, 1], [1]], [[n]]) ≒ F [ωω ](n)
Ak([..., [3, a3], [2, a2], [1, a1], [0, a0]], [[n]]) = Ak([..., a3, a2, a1, a1], [n])
ωω
Ak([[n 個の 1], [1]], [[n]]) ≒ F [ωω
4 重リスト
](n)
Ak([[[1, 0, 1], [1]], [[1]]], [[[n]]]) ≒ F [ω∧∧ 4](n)
2
ωω
Ak([[[1, 0, 0, 1], [1]], [[1]]], [[[n]]]) ≒ F [ωω
](n)
ωω
ω3
Ak([[[1, 0, 0, 0, 1], [1]], [[1]]], [[[n]]]) ≒ F [ω
](n)
Ak([[..., [3, a3], [2, a2], [1, a1], [0, a0]]], [[[n]]]) = Ak([[..., a3, a2, a1, a1]], [[n]])
Ak([[[n 個の 1], [1]], [[1]]], [[[n]]]) ≒ F [ω∧∧ 5](n)
n 重リスト
n 重リストとすることで F [ε0 ](n) に到達
6.5
ふぃっしゅ数バージョン 5
バージョン 3 の次は、バージョン 4 ではなくバージョン 5 の説明をします。巨大数探索スレッドでは、
バージョン 4 が先に登場するのですが、この文章では、章を進めるにしたがってより大きな数、関数が登
場するように記述するため、バージョン 5 よりも大きいバージョン 4 の説明は後回しにします。
「関数から関数への写像を考える」という考えをさらにすすめると、「関数から関数への写像」から「関
数から関数への写像」への写像を考えることができます。では、このような写像に対して写像を適用する回
数の数え上げを定義する事はできないでしょうか。このような考察を進めた結果、以下の様なふぃっしゅ数
バージョン 5 が定義されました。
2 再掲：巨大数探索スレッド
7-571 でアップされた文書 (たろう, 2007 年 10 月 17 日) http://gyafun.jp/ln/archive/7-571.txt
6.5. ふぃっしゅ数バージョン 5
63
【定義】ふぃっしゅ数バージョン 5
[1] 集合 Mn (n = 0, 1, 2, ...) を以下のように定める。
M0 =自然数の集合
Mn+1 =写像 Mn → Mn 全体の集合
Mn の元を Mn 変換と呼ぶ
[2] Mn 変換 m(n) (n ≧ 1) を以下のように定める。
fn ∈ M(n) に対して、m(n + 1)(fn ) = gn を以下で定める。
fn−1 ∈ M (n − 1) に対して、gn (fn−1 ) = gn−1 を以下で定める。
fn−2 ∈ M (n − 2) に対して、gn−1 (fn−2 ) = gn−2 を以下で定める。
……
f0 ∈ M (0) に対して、g1 (f0 ) = g0 を以下で定める。
g0 =(..((fnf0 fn−1 )fn−2 )...f1 )f0
すなわち
m(1)(f0 )
=
f0 f0
(m(2)f1 )f0
=
(f1 f0 )(f0 )
(..((m(n + 1)fn )fn−1 )...f1 )f0
:=
(..(fn f0 fn−1 )...f1 )f0
[3] ふぃっしゅ関数 F5 (x) を以下のように定める。
F5 (x) := ((..((m(x)m(x − 1))m(x − 2))...m(2))m(1))(x)
[4] ふぃっしゅ数 F5 := F563 (3) とする。
定義 [2] より、m(1)(x) := xx です。また、
(m(2)f )(x) = (f x )(x)
となりますから、m(2) は F3 における s(1) の定義と一致し、
m(2) = s(1)
となります。さらに、
((m(3)m(2))f )(x)
= (m(2)x f )(x)
= (s(1)x f )(x)
= (s(2)f )(x)
すなわち、m(3)m(2) = s(2)
((m(3)2 m(2))f )(x) = ((m(3)(m(3)m(2)))f )(x)
第 6 章 証明可能帰納関数
64
= ((m(3)m(2))x f )(x)
= (s(2)x f )(x)
= (s(3)f )(x)
すなわち、m(3)2 m(2) = s(3)
m(3)n m(2) =
m(4)m(3)m(2) =
s(n + 1)
ss(1)
といったように、計算ができます。すなわち、m(3) は操作の対角化で、m(2)=s(1) の原始帰納に対して、
m(3) を繰り返し適用することで m(3)n m(2) = s(n + 1) の多重帰納が生成されます。それを数え上げるの
が m(4) ということです。
ハーディー関数との対応を考えると、m(2) の定義から f(x) ≒ F[α](x) の時、m(2)f (x) ≒ F [α + 1](x)
となりますが、これを m(2) = F [+1] と便宜的に表記することとします。すると、
m(3)m(2) =
s(2) = F [+ω]
m(3)m(3)m(2) =
s(3) = F [+ω2 ]
m(3)a m(2) =
s(a) = F [+ωa ]
m(4)m(3)m(2) =
ss(1) = s(x) = F [+ωω ]
となります。さらに、
=
ss(2) = F [+ωω+1 ]
m(3)2 [m(4)m(3)]m(2) =
ss(3) = F [+ωω+2 ]
m(3)a [m(4)m(3)]m(2) =
2
m(4)m(3) m(2) =
ss(a + 1) = F [+ωω+a ]
m(3)[m(4)m(3)]m(2)
ss(n) = F [+ωω× 2 ]
ここまでが、F3 の定義で記述できるところです。さらに、F3 の拡張である多変数化した s(x) を使うことで、
2
m(4)m(3) m(2)
3
m(4)m(3) m(2)
a
m(4)m(3) m(2)
m(4)2 m(3) m(2)
m(3) m(4)2 m(3) m(2)
m(4)m(3) m(4)2 m(3) m(2)
2 m(4)m(3) m(4)2 m(3) m(2)
3 m(4)m(3) m(4)2 m(3) m(2)
2
m(4)2 m(3) m(2)
3
m(4)2 m(3) m(2)
=
=
=
=
=
=
=
=
=
=
3
m(4) m(3)m(2) =
m(4)4 m(3)m(2) =
m(5)m(4)m(3)m(2) =
ss(n) = s(1, 3, 1) = F +ωω× 2
s(1, 4, 1) = F +ωω× 3
s(1, a + 1, 1) = F +ωω× a
2
s(2, 1, 1) = F +ωω
2
s(2, 1, 2) = F +ωω +1
2
s(2, 2, 1) = F +ωω +ω
2
s(2, 3, 1) = F +ωω +ω×2
2
s(2, 4, 1) = F +ωω +ω×3
2
s(3, 1, 1) = F +ωω ×2 (x)
2
s(4, 1, 1) = F +ωω ×3 (x)
3
s(x, 1, 1) = F +ωω
4
s(x, 1, 1, 1) = F +ωω
ω
s(1, 1, ...(1 が x 個), 1, 1) = F +ωω
6.6. バードの多重リスト表記
65
このように計算されます。
これまでの計算から、
m(3)m(2) =
m(4)m(3)m(2) =
F [+ω]
F [+ωω ]
ω
m(5)m(4)m(3)m(2) =
F [+ωω ]
m(6)m(5)m(4)m(3)m(2)
=
F [+ω∧∧ 4]
m(7)m(6)m(5)m(4)m(3)m(2)
=
F [+ω∧∧ 5]
となり、同様に
…
となることが期待されます。この時、
F5 (x) ≈ F [ε0 ]
となります。
6.6
バードの多重リスト表記
さて、ここでバード氏が再び登場します。巨大数探索スレッドでは、ふぃっしゅ数に対してバード数が見
つけられて、魚と鳥の対決だと盛り上がっていましたが、バード氏は日本の掲示板でそんなことで盛り上
がっているとはまったく知らなかった事でしょう。そのバード氏のバード数のページはなくなり、巨大数の
探求は終わっていたかに見えました。ところが、バード氏は、海外のグーゴロジスト達といっしょにさらに
巨大数の探求を進めていました。
バード氏は、ロバート・ムナフォ氏のサーバーの上に、巨大数のページ3 を開設し、古いバード数よりも
大きな巨大数を作っていました。相変わらず、かなり複雑な定義をしていますが、順序数に関する勉強もし
ていて、自作の巨大数を順序数と対応付けながら検証しています。古いバード数の時には、バード氏のペー
ジには順序数の記述はなかったので、その後グーゴロジスト達で議論が深まって来たのだと思います。
バード氏のホームページには、いくつかの段階を持って巨大数が定義されています。ここでは、概略を
記します。まず最初に、 バードの多変数関数 (Bird’s linear notation) を考えています。古いバージョンで
は、チェーン表記を元にチェーンを回転させたりしていましたが、今度は帰納の方法を変えたようです。多
ω
変数アッカーマンと比べると複雑な定義ですが、H[ωω ] = F [ωω ] のレベルに到達したようです。多変数
アッカーマンと同程度、ということになります。これを、バード氏は順序数ωのレベルとしています。ま
た、この多変数関数で 5 変数以上になるとチェーン表記を越えることの証明もしているので、チェーンは
変数が増えてもたいしたことはない、ということに気がついたようです。
その次に、 バードの多次元配列表記 (Bird’s multi-dimensional array notation) を定義しました。これ
ω
は、2 次元、3 次元、そして多次元の配列を表記する方法です。これで、F [ωω ] の段階に上がったとして
います。さらに、 バードのハイパー次元配列表記 (Bird’s hyper-dimensional array notation) と多次元を
ωω
越えるハイパー次元を定義しました。これで、F [ωω
3 Chris
] になったようです。
Bird’s Super Huge Numbers http://mrob.com/users/chrisb/
第 6 章 証明可能帰納関数
66
そしていよいよ、 バードの多重リスト表記 (Bird’s nested array notation) を考えて、これが F [ε0 ] に
到達した、としています。これはちょうど、多重リストアッカーマン関数が F [ε0 ] に到達したのと同じこ
とでしょう。これは、多次元配列やハイパー次元配列が、それぞれ自分自身を中に含むようにネスト構造を
持ちます。バードの計算では、
[1[2]2] = ω^ω^ω
[1[3]2] = ω^ω^ω^2
[1[n+1]2] = ω^ω^ω^n
[1[1,2]2] = ω^ω^ω^ω = ω^^4
[1[1[2]2]2] = ω^^5
といったように（バードは F 関数よりもωが 1 つ少ない表記を使っているので、ωを増やして F 関数に
直しました）、入れ子レベルが上がると ω∧∧ n の n が上がって、入れ子レベルを対角化すると ε0 になると
いうことのようです。ここで、[] はハイパー次元表記なので、多重リストの中にハイパー次元が入っている
ということになります。多重リストに ω∧ を増やす力があるのであれば、複雑なハイパー次元配列を持ち
出さなくても、多変数配列を元に多重リスト構造を作れば、同じように ε0 をあらわすことができそうな気
がします。
6.7
ヒドラゲーム
本節では、ヒドラゲームについて記します。その前に、グッドスタイン数列の話の続きをします。
グッドスタイン数列の話 (2.6 節、p.20) が、ずっと放置されてきました。ようやく、続きを話すことがで
きます。n で始まるグッドスタイン数列が終了するまでのステップ数を返す グッドスタイン関数 G(n) の大
きさは、なんと H[ε0 ] のレベルなのです。数列の定義は原始帰納なのに、関数はこんなに大きくなる、実
に面白い関数です。
グッドスタイン数列は急激に増加しますが、やがて減少に転じ、必ず 0 となって数列が終わる事が証明
されています。これを グッドスタインの定理 (Goodstein’s theorem) と言います。なぜ、必ず 0 になるの
でしょうか。それは、このように証明します。
グッドスタイン数列の遺伝的記法で、数字の底のところを順序数ωで書き換えます。この時、nk の和で
書かれていればそのまま ωk に書き換えるだけですが、ak nk の和で書かれている場合は、ωk × ak と書き
換えます。
19 ではじまるグッドスタイン数列を、そのように書き換えてみます。
ω
2
G0 (19)
= 22 + 2 + 1 → ωω + ω + 1
G1 (19)
=
33 + 3 → ωω + ω
G2 (19)
=
44 + 3 → ωω + 3
G3 (19)
=
55 + 2 → ωω + 2
G4 (19)
=
66 + 1 → ωω + 1
G5 (19)
=
77 → ωω
3
ω
4
ω
5
ω
6
ω
7
ω
6.7. ヒドラゲーム
67
対応する順序数を見ると、どんどん小さくなっています。これは、グッドスタイン数列での 2 つの演算のう
ち、底を変換する演算は底をωにしてしまったため変わらず、1 を引く演算によって、より小さい順序数と
a
なるためです。G6 (19) については、非常に長い順序数の式が並ぶことになりますが、ΣωΣ(ω
k
に書けます。もともとの数列を n の和の形で書いていれば、Σω
Σω
a
ω
ω
の形になり、ω
×b)
× c の形
よりも小さくなっ
ています。
順序数の重要な性質として、下降数列（どんどん小さくなる数列）を取ると、必ず有限回数で 0 になる、
ということがあります。したがって、必ずグッドスタイン数列は有限ステップで値が 0 になって終了します。
さて、このようにしてグッドスタインの定理が証明されましたが、一方で、Kirby and Paris (1982)
4
は、
ペアノ算術の演算をもってしては、グッドスタインの定理は証明出来ない、ということを証明しました。す
でに証明されていることが証明出来ないとはおかしな話ですが、上の証明ではペアノ算術から外れたロジッ
クを使ったために、証明できたということです。
Kirby らは、論文でこの証明をする時に、 ヒドラゲーム (Hydra battle) を考えました。ヒドラゲーム
とは、ギリシア神話に登場するヘラクレス (Hercules) とヒドラ (Hydra) の戦いにヒントを得たもので、ヒ
ドラは巨大な胴体とたくさんの首を持ち、１本の首を切り落としても、すぐにそこから新しい 2 本の首が
生えてきます。
そこで、このようなヒドラを考えます。ヒドラは、図 6.1 のように有限の樹の構造を持っていて、複数の
ノード (node) がセグメント (segment) で結ばれています。樹の根元はルート (root) と呼び、すべてのノー
ドは下に１つずつセグメントを降りて行くと、必ずルートに到達します。そして、一番上のノードをトップ
ノード (top node) と呼び、トップノードにつながれているセグメントを首 (head) と呼びます。
図 6.1: ヒドラの構造。Kirby and Paris (1982) から引用。
ヒドラゲームはこのようなルールです。ヘラクレスは、ヒドラの首 (head) を 1 回につき 1 つ切り落とし
ます。n 回目に切り落とした時に、ヒドラは n 個の頭が生えます。その生え方は、今、切り落とした首から
セグメントを 1 つ下に降ります。そのセグメントから上に伸びている樹の形と同じ形の樹の構造が、今度は
そこからさらに 1 つノードをセグメントを下に降りたノードから n 個コピーされます。ここで、それ以上
ノードが下がれないときには、首が生えません。
ヒドラゲームは図 6.2 のように進行します。図では、切り落とす首が矢印で示されています。左上の図が
最初のヒドラの構造で、首を切り落とすと、after stage 1 の形になります。これは、切り落とした首の 1
つ下のノードから上を見たときの V 字構造が 1 つ、さらに 1 つ下のノードからコピーされました。次に、
4 Kirby, L.; Paris, J. (1982), ”Accessible independence results for Peano arithmetic”, Bulletin of the London Mathematical
Society 14: 285-293. http://logic.amu.edu.pl/images/3/3c/Kirbyparis.pdf
A top node of a hydra is one which is a node of only one segment, and is not the
root. A head of the hydra is a top node together with its attached segment.
A battle between Hercules and a given hydra proceeds as follows: at stage n
(n ^ 1), Hercules chops off one head from the hydra. The hydra then grows n "new
heads" in the following manner:
From the node that used to be attached to the head which was just chopped off,
traverse one segment towards the root until the next node is reached. From this node
sprout n replicas of that part of the hydra (after decapitation) which is 第
"above"
68
6 章 the証明可能帰納関数
segment just traversed, i.e., those nodes and segments from which, in order to reach
the root, this segment would have to be traversed. If the head just chopped off had
stage 2 では切り落とした首の
2 つ下のルートノードから、今度は
2 つコピーされます。次は 3 つ、次は 4
the root as one
of its nodes, no new head is grown.
Thus the battle might for instance commence like this, assuming that at each
つとコピーされる数が増えるので、ヒドラはどんどん増殖します。
stage Hercules decides to chop off the head marked with an arrow:
after stage 3
after stage 2
図 6.2: ヒドラゲームの進行。Kirby and Paris (1982) から引用。
ヘラクレスは、有限の回数首を切ることで、ルート以外のすべてを切り落とす事ができればこのゲームに
勝ちます。どのような順番で首を切れば、勝つ事ができるでしょうか。実は、どの順番で切っても勝つこと
が分かります。どうしてでしょうか。
ヒドラの構造で、各ノードを順序数に割り当てます。トップノードには 0 を、他のノードには、その上の
ノードに割り当てられる順序数 α1 ≥ · · · ≥ αn に対して、ω α1 + · · · ω αn を割り当てます。先ほどのヒドラ
ω
の構造図 6.1 で、一番左上のノードから下に降りると、0 → 3 → ωω + ω3 →ωω
+ω3
2
+ ωω
+1
のように
割り当てられます。この時、ルートに割り当てられた順序数が、ヒドラに対応づけられる順序数です。
ヘラクレスがどのような順番で首を切っても、必ずヒドラの順序数は小さくなります。グッドスタイン数
列の時には、順序数が小さくなる道順が一つに決まりましたが、ヒドラゲームでは自由に順路を選ぶ事が
できます。グッドスタイン数列もヒドラゲームもともに、最初は爆発的に増加するけれど最後はなくなって
しまうこと、順序数と対応付けると順序数が小さくなること、といった意味で共通しています。
Kirby and Paris (1982) は、ヒドラゲームと対応付けながら、G(n) が H[ε0 ] と同じだけの増加速度を持
つこと、もっと正確には、α < ε0 以下の全ての順序数αに対して、G(n) が H[α] よりも増加速度が速い
ことを証明しました。Dershowitz and Moser (2007)
5
は、ヒドラゲームでヘラクレスが何回首を切れば勝
てるか、という関数は、ヒドラの順序数に対するハーディー関数に対応する事を示しました。つまり、カン
トールの標準形で書く事のできるどんな順序数αを持って来ても、それよりも大きな順序数のヒドラがあ
ると説明しました。
ヒドラゲームのプログラム6 もあります。
本章では、色々な ε0 レベルの関数を見てきました。カントールの標準形をヒドラのようなツリー構造
で書くと、たろう氏やバード氏が考えついたように多重リスト構造に行き着きます。多変数関数では、ヒド
5 Dershowitz and Moser ”The Hydra Battle Revisited”, Rewriting, Computation and Proof.
Lecture Notes
in Computer Science Volume 4600, 2007, pp 1-27 http://dx.doi.org/10.1007/978-3-540-73147-4 1 free download:
http://www.cs.tau.ac.il/ nachum/papers/LNCS/Hydra.pdf
6 The hydra game (Andrej Bauer) http://math.andrej.com/2008/02/02/the-hydra-game/
6.7. ヒドラゲーム
69
ラのルートから 1 つ上に変数をたくさん書くまでしかできませんが、それぞれの変数からさらに上に多変
数関数の変数を延ばして行くネスト構造を作ったわけです。
それに対して、ふぃっしゅ数バージョン５は、m(2) → m(3) → m(4) と、操作の対角化を繰り返すことで
ヒドラのセグメントを上に上がって行きます。下から数えて n 番目のトップノードが、m(n) に対応します。
[m(4)m(3)]3 [m(4)2 m(3)]m(2) = s(2, 4, 1) = F [+ωω
2
+ω×3
]
の計算を見ると、[m(4)m(3)] の部分は ω × 3 に対応し、m(4)2 は 2 に、m(4)2 m(3) は ω2 に対応し
3
ます。ヒドラの構造図 6.1 の場合は、一番左上のトップノードは、ルートから上に 3 個上がったところ
なので m(3) です。その下のノードは、上に m(3) が 3 つついていて、自身が m(2) なので、m(3)3 m(2)
になります。その 1 つ下のノードは、m(3)3 m(2) と m(4)m(3)m(2) がついている m(1) ノードなので、
[m(3)3 m(2)][m(4)m(3)m(2)]m(1) です。そして、一番下のルートノードは
[m(2)[m(3)2 m(2)]m(1)] [[m(3)3 m(2)][m(4)m(3)m(2)]m(1)] (x)
となります。
巨大数研究室の「ゼミの成果」7 には、「ppt で目で見るヒドラゲーム」として、巨大数勉強会（2007 年
11 月 3 日、文京区シビックセンター）でポチさんが発表されたスライドがアップされています (ppt ファイ
ルを zip で圧縮）。その中に、ハーディー関数とヒドラゲームの関係、ヒドラゲームの様子、ふぃっしゅ数
バージョン 5 の計算過程のハーディー関数やヒドラゲームとの対応、次章で出てくる Veblen 関数による拡
張ヒドラゲーム等が、図解されています。そのファイルをダウンロードしてスライドを見ながら、このヒド
ラゲームの節を読み返すと、より分かりやすいと思います。
以上をまとめると、証明可能帰納関数は、カントールの標準形のハーディー関数で書くことができて、そ
の構造をヒドラのようなツリー構造図で書くことができます。その構造を延ばして行く関数を作る事で、あ
らゆる証明可能帰納関数の増加を越える ε0 レベルの関数を作る事ができます。その時には、ツリーを上に
延ばす時に、下のノードを数え上げる操作が含まれている必要があります。グッドスタイン関数はその教科
書的な例ですが、たろう氏やバード氏が作成した多重リスト構造は関数のネスト構造で、ふぃっしゅ数バー
ジョン 5 は操作の対角化をあらわす m(n) で、その構造を作りました。それぞれ、ハーディー関数と対応さ
せながら、カントールの標準形を構成していることを確認しています。
7 巨大数研究室
- ゼミの成果 http://www.geocities.co.jp/Technopolis/9946/result.html
70
第 7 章 帰納関数
7.1
η0 以下の順序数
前章までで、H[ε0 ] までの巨大関数を作成することができました。H[ε0 ] よりも大きな帰納関数につい
て扱います。ここから、さらに大きな順序数をどのように定義するかを見ながら、対応する巨大関数の作
成に挑みます。ここから先は、さらに順序数の定義が複雑になり、また対応する関数の定義も複雑になり
ます。
ハーディー関数では極限順序数に対応する関数の定義に、順序数の基本列の定義を使っています。順序数
の中には、基本列が定義できないものや、基本列の定義の中に基本列で定義できない順序数を使っているも
のがあります。帰納的に定義された関数であれば、帰納的に定義出来る順序数のハーディー関数として表現
出来るはずです。
それでは、ε0 以上の順序数について見ていきます。ε0 は、α = ωα が成り立つ最小の順序数です。ε
ε0 +1
0
よりも大きく α = ωα が成り立つ最小の順序数は ε1 と書かれ、ε0 + 1, ωε0 +1 , ωω
持つ極限順序数です。ここで、この収束列を a0 ,a1 ,a2 ,... として計算します。an+1 = ω
この基本列と、bi = ε0
∧∧
a0
=
ε0 + 1
a1
=
ωε0 +1 = ωε0 ×ω = ε0 ×ω
a2
=
ωε0 ×ω = (ωε0 )ω = ε0
a3
=
ωε0 = ωε0
a4
=
ωε0
ω
ε0 ω
1+ω
= ωε0
... を収束列に
です。
ω
ω
= ωε0 ×ε0 = ε0
1+ε0 ω
an
= ε0
i、つまり b0 = 1, b1 = ε0 , b2 = ε0
ε 0 ε0
∧∧
ε0 ω
ω
2 = ε0
ε0
, b3 = ε0
∧∧
3, … の基本列を
比較すると、i > 1 で bi−1 < ai < bi となるため収束先は一致し、aω = bω となります。したがって、
ε1 = aω = bω = ε0
∧∧
ω
となります。このように、基本列の取り方は一通りではありません。そして、ωε1 = ε1 が成り立ちま
す。α = ωα が成り立つ順序数は、順番に ε0 , ε1 , ε2 ... と定義されます。つまり、
εi+1
= lim(εi + 1, ωεi +1 , ωω
= εi
∧∧
εi +1
, …)
ω
となります。次に、lim(ε0 , ε1 , ε2 , …) の収束列を取ると、極限順序数 εω が定義され、これは α = ω
α
が成り立つω番目の順序数です。
さらに、基本列の定義を繰り返し、εω ,εωω ,εωωω ,... という基本列に到達したところで、α = ωα が
成り立つ ε0 番目の順序数 εε0 が定義されます。
そして、ε0 、εε0 、εεε 、εεε
0
ε0
、といった基本列を取ると、極限順序数 η0 が定義されます。η0
は、α = εα が成り立つ最小の順序数です。
7.2. ふぃっしゅ数バージョン 6
7.2
71
ふぃっしゅ数バージョン 6
ふぃっしゅ数バージョン 6 (F6 ) と同時に定義されるふぃっしゅ関数バージョン 6 は、H[η0 ] 程度の大き
さを持ちます。
【定義】ふぃっしゅ数バージョン 6
[1] 集合 M [m, n](m = 0, 1, ...; n = 1, 2, ...) を以下のように定める。
M [0, 1]=自然数から自然数への関数
M [m + 1, 1]=M(m,n) (n=1,2,...) の元 1 個ずつを要素に持つ集合
M [m, 1] の元は、その要素の要素の…要素である M [0, 1] の元と同じ関数の働き
を持つ。
M [m, n + 1]=写像 M [m, n] → M [m, n] 全体の集合 (n=1,2,...)
[2] M [m, n] の元 m(m, n) を以下のように定める。ただし、ai , bi , fi は m(m,i) の元とし、厳密な定義
の構造は F5 と同じである。
m(0, 1)(x)
m(m, n + 1)fn fn−1 ...f1 (x)
:= x + 1
:= fn x fn−1 ...f1 (x)
(m = 0; n = 1, 2, ...および m = 1, 2, ...; n = 2, 3, …)
m(m + 1, 1)
:=
[m(m, 1), m(m, 2), m(m, 3), …]
m(m + 1, 2)[a1 , a2 , ...]
:=
[b1 , b2 , …] の bn を以下で定める。
bn fn−1 ...f1 (x)
:= ay ay−1 ...an fn−1 …f1 (x)(y = max(x, n))
[3] ふぃっしゅ関数 F6 (x) を以下のように定める。
F6 (x) := m(x, 2)m(x, 1)(x)
[4] ふぃっしゅ数 F6 := F663 (3) とする。
F6 の大きさは、以下の様に計算できます。
=
[m1 , m2 , m3 , …](mi = m(0, i))
=
x+1
m(1, 2)m(1, 1)
=
[a1 , a2 , a3 , …] とすると
a1 (x)
=
mx mx−1 ...m1 (x) より、F5 と同様の計算で
a1
≈
H[ε0 ]
すなわち m(1, 2)m(1, 1)
≈
H[ε0 ]
a2 f1 (x)
=
my my−1 …m2 f1 (x)(y = max(x, 2)) より
m2
=
H[×ω](H[a] → H[a ×ω] の変換)
m(1, 1)
第7章
72
m3 m2
=
H[×ωω ]
m3 m3 m2
=
H[×ωω ]
m4 m3 m2
=
H[×ωω ]
m5 m4 m3 m2
=
H[×ωω
帰納関数
2
ω
ωω
]
…
a2
H[×ε0 ]
=
となります。そして、
a3 f2 f1 (x)
=
my my−1 ...m3 f2 f1 (x)(y = max(x, 3)) より、
f2
=
H[× a] とすると
m3 f2
=
H[× aω ]
m3 m3 m2
=
H[× aω ]
m4 m3 f2
=
H[× aω ]
m5 m4 m3 f2
=
H[× aω
2
ω
ωω
]
…
a3 f2
=
H[× aε0 ]
となるため、a3 は H[× a] → H[× aε0 ] の変換です。
a4 f3 f2 f1 (x)
=
my my−1 ...m4 f3 f2 f1 (x)(y = max(x, 4)) より、
f2
=
H[× a]、f3 = H[× a] → H[× ab ] の変換とすると
f2
=
H[× a]
f3 f2
=
H[× ab ]
m4 f3 f2
=
H[× ab ]
m5 m4 f3 f2
=
H[× ab
ω
ωω
]
…
a4 f3 f2
:
ε0
H[× ab ]
となるため、a4 は [H[× a] → H[× ab ]]→ [H[× a] → H[× ab
a4 a3
a4 a3 a2
ε0
]] の変換です。このことから、
ε
ε0 0
: H[× a] → H[× a
: H[×ε0
ε0
ε0
] の変換
]
c
と計算され、以下同様に a5 は [H[× a] → H[× ab ]]→ [H[× a] → H[× ab ]] → [H[× a] → H[× ab ]]→ [H[
× a]→ H[× ab
cε0
]] の変換となって、
a5 a4 a3 a2
a6 a5 a4 a3 a2
an+1 an ...a2
: H[×ε0
ε0 ε0
: H[×ε0
∧∧
: H[×ε0
∧∧
ε0
5]
n]
] = H[×ε0
∧∧
4]
7.2. ふぃっしゅ数バージョン 6
73
と計算され、
m(1, 2)2 m(1, 1) ≈ H[ε0
となります (ε1 = ε0
∧∧
∧∧
ω] = H[ε1 ]
ωの計算は前節)。
m(1, 2)3 m(1, 1) = [b1 , b2 , b3 , ...]
とすると、bi は上記 ai の ε0 を ε1 に変えた式となります。したがって、
m(1, 2)3 m(1, 1) ≈ H[ε1
∧∧
ω] = H[ε2 ]
m(1, 2)4 m(1, 1) ≈ H[ε2
∧∧
ω] = H[ε3 ]
といったように、m(1, 2) は H[εa ] の a に 1 を足す効果を持ちます。このことから、F5 の計算と同様の構
造で、
≈ H[εω ]
m(1, 3)m(1, 2)m(1, 1)(x)
≈ H[εωω ]
m(1, 4)m(1, 3)m(1, 2)m(1, 1)(x)
≈ H[εωωω ]
m(1, 5)m(1, 4)m(1, 3)m(1, 2)m(1, 1)(x)
m(1, x)m(1, x − 1)...m(1, 2)m(1, 1)(x)
≈ H[εε0 ]
m(2, 2)m(2, 1) ≈ H[εε0 ]
となります。そして、m(2, 2)m(2, 1) = [f1 , f2 , f3 , …] とすると (fi は M [1, i] の元)
f1
= H[εε0 ] 程度の関数を元に持つ M (1, 1)
f2
:
H[ε×ε0 ](H[εa ] → H[εa ×ε0 ] の変換)
f3
:
H[ε× a ] → H[ε× aε0 ] の変換
f4 f3 f2
:
H[ε
×ε0 ε0
ε0
]
となることから、
m(2, 2)2 m(2, 1) ≈ H[εε1 ]
m(2, 2)3 m(2, 1) ≈ H[εε2 ]
m(2, 2)4 m(2, 1) ≈ H[εε3 ]
と計算されます。このように、m(2,2) が H[εεa ] の a に 1 を足す効果を持つので、
m(3, 2)m(3, 1) ≈ H[εεε0 ]
となります。
以上の計算を繰り返すと、
m(1, 2)m(1, 1) ≈
H[ε0 ]
m(2, 2)m(2, 1) ≈
H[εε0 ]
m(3, 2)m(3, 1) ≈
H[εεε0 ]
m(4, 2)m(4, 1) ≈
H[εεε
ε0
]
第7章
74
帰納関数
となり、
F6 (x) = m(x, 2)m(x, 1)(x) ≈
H[η0 ]
と計算されます。
7.3
ヴェブレン関数
本書の中でも、ここから先の議論は難しくなってきますので、著者の記述の正確性はかなり怪しくなって
きます。現時点での理解を書いておきます。
ヴェブレン関数 (Veblen function) φα (β) は以下の様に定義されます (Wikipedia の説明1 , Veblen の
原著論文2 )。
【定義】ヴェブレン関数
φ0 (β) = ωβ
φα+1 (β) =「φα (γ) = γ となる γ」 のうち β 番目のもの
φα (β) = 「すべての α0 < α に対し φα0 (γ) = γ となる γ」 のうち β 番目のもの (αは極限順
序数)
φα (β) < φγ (δ) となるのは、「α = γ かつ β < δ」であるか、または「α < γ かつ β < φγ (
δ)」であるかまたは「α > γ かつ φα (β) < δ」の時だけである。
φα (0) = α を満たす最小の順序数はフェファーマン・シュッテの順序数 (Feferman-Sch¨
utte ordinal)
と呼ばれ、Γ0 と書かれる。
Veblen 関数の定義 φα+1 (β) =「φα (γ) = γとなるβ番目の数」は、「ある順序数γより小さい数に
+, φ0 , φ1 , …, φα を何回適用してもやはりγより小さい」という条件を満たすγのうちβ番目のものとし
ても同じことです。
「 」の条件は、
「γより小さい数は +, φ0 , φ1 , …, φα という演算について閉じている」
と言い換えることもできます。
(1) φ0 (α) の計算
まずは、φ0 (α) = ωα について考えます。
α=0 のときは ω0 = 1 より小さい数は 0 しか存在せず、0 をいくら足し合わせても 1 よりは小さいこと
から、1 が「その数より小さい数は+について閉じている」ような 0 番目の (最初の) 数ということになり
ます。
α=1 のときは、ω1 = ω より小さい数 (つまり自然数) をいくら足し合わせてもωよりは小さいというこ
とになります。逆に考えると、自然数をいくら足し合わせても到達できないような最小の数を φ0 (1) = ω
として定義していることになります。
α=2 のときは、φ0 (2) は 2 番目の数であるため 1 番目の数であるωよりは大きな数となります。なので、
自然数やωをいくら足し合わせても到達できないような最小の数を考えると、それは ω × n の収束先であ
る ω2 ということになります。
1 Wikipedia
- Veblen function https://en.wikipedia.org/wiki/Veblen function
Oswald (1908), ”Continuous Increasing Functions of Finite and Transfinite Ordinals”, Transactions of the
American Mathematical Society 9 (3): 280-292 http://dx.doi.org/10.1090/S0002-9947-1908-1500814-9
2 Veblen,
7.3. ヴェブレン関数
75
α=3 のときは、φ0 (3) は 3 番目の数であるため 2 番目の数である ω2 よりは大きな数となります。自然
数やωや ω2 をいくら足し合わせても到達できないような最小の数を考えると、それは ω2 × n の収束先で
ある ω3 ということになります。
同様に、φ0 (4) = ω4 , φ0 (5) = ω5 , …, φ0 (n) = ωn となり、さらに
φ0 (φ0 (1)) = φ0 (ω) = ωω
ω
φ0 (φ0 (φ0 (1)))= φ0 (ωω ) = ωω
のように、ヴェブレン関数によって順序数が定義されます。
(2) φ1 (α) の計算
次に、φ1 (0) を考えます。これは、
「φ0 (α) = αとなるα のうち最初のもの」つまり「ωα = α となる
最初のα」です。これが、ε0 の定義でした。また、ε0 より小さい数に+や φ0 を何回適用しても ε0 よ
り小さいということになります。0 に+や φ0 を何回適用しても到達できないような数のうち、最小のもの
を φ1 (0) = ε0 と定義していると言うこともできます。これはつまり、カントール標準形では書くことが
できない最小の順序数、ということです。
φ1 (1) = ε1 は、ε0 以下の数 (ε0 も含む) に+や φ0 を何回適用しても到達できない最小の数というこ
とになります。ε1 = ε0
∧∧
ω ですから、ε0 に冪乗を繰り返しても到達できない数です。
以下、φ1 (2) = ε2 , φ1 (3) = ε3 , …, φ1 (α) = εα と定義され、さらに
φ1 (φ1 (0)) = φ1 (ε0 ) = εε0
φ1 (φ1 (φ1 (0)))= φ1 (εε0 ) = εεε
0
と計算することができます。
(3) φ2 (α) の計算
φ2 (0) は、「φ1 (γ) = γ となる γ のうち最初のもの」つまり、「εγ = γ となる最初の γ」となりま
す。0 に+と φ0 と φ1 を何回適用しても到達できない最小の数です。そのような順序数は、η0 になります。
そして、εα = α となるα番目の順序数が、 φ2 (α) = ηα で定義されます。
巨大数スレッド 9
3
で、ヴェブレン関数の定義と収束列がまとめられています。なお、この定義の中で無
限基数（可算基数＝超限基数では弱すぎるので、不可算基数、つまり不可算順序数のことか？）が使われて
いるのは、次節の Bachmann-Howard 順序数でΩが導入されていることと同じ理由だと推察されます。
このように、+だけでは到達できない数を φ0 で定義し、+と φ0 だけでは到達できない数を φ1 で定義
し、+と φ0 と φ1 だけでは到達できない数を φ2 で定義し、…とやっていって、最終的にはヴェブレン関
数を何回使っても到達できない最小の数をフェファーマン・シュッテの順序数 Γ0 と定義しています。
ヴェブレンは、2 変数関数の定義を多変数 φ (αn , αn − 1 , …, α0 ) に拡張しています。定義は、先ほど引
用した Wikipedia または Veblen の原著論文を参照して下さい。多変数ヴェブレン関数に対して、
3 巨大数探索スレッド
φ (1, 0, 0)
= Γ0
φ (1, 0, γ)
= Γγ
9 の 74 にアップされた文書 (2010 年 12 月 6 日) http://gyafun.jp/ln/archive/9-74.txt
第7章
76
φ (1, 0, 0, 0)
φ (1, 0, …, 0)(ω個の 0)
帰納関数
= アッカーマン順序数 (Ackermann ordinal)
= 小ヴェブレン順序数（Small V eblen ordinal
となります。
ヴェブレンはさらに、変数の数を超限的にたくさん増やしたとき (transfinitely many variables) にも、
ヴェブレン関数を定義できるとしています。この定義の限界が大ヴェブレン順序数 (Large Veblen ordinal)
とされています。
Bachmann-Howard 順序数
7.4
バッハマン・ホワード順序数 (Bachmann-Howard ordinal) は、フェファーマン・シュッテの順序数より
も大きい帰納的な順序数です。この順序数を定義するための順序数崩壊関数 (ordinal collapsing function)
ψ は、Wikipedia
4
に記されています。ここでは、その概略を記します。
Bachmann-Howard 順序数を定義するためには、順序数崩壊関数Ψを使います。ここでのポイントは、Ψ
関数の引数として帰納的に定義できない順序数Ωを使うことです。通常は、Ωとして濃度が不可算となる最
を使っても構わないようで
初の順序数 ω1 が用いられますが、帰納的に定義できない最初の順序数 ωCK
1
す。Ψ関数は帰納的でない順序数を計算に用いていますが、その結果計算される順序数は帰納的な順序数に
なります。ここが、非常にトリッキーなところです。Ωを用いないと φ2 (0) = η0 よりも大きな順序数 φ
2 (1)
をψ関数でうまく定義できない（ψ関数の値が η0 よりも大きくならない）ところを、Ωを導入する
ことでその壁を突破するために使われているようです。η0 よりも大きい順序数を扱う時には注意が必要と
なりそうです。
Wikipedia によれば、Ψ関数は以下のような順序数に対応します。
ψ(ΩΩ ) = Γ0 フェファーマン・シュッテの順序数
2
ψ(ΩΩ ) アッカーマン順序数
ω
ψ(ΩΩ ) 小ヴェブレン順序数
Ω
ψ(ΩΩ ) 大ヴェブレン順序数
ψ(εΩ+1 ) Bachmann-Howard 順序数
7.5
さらに大きな順序数
Wikipedia の記述5 にしたがって、さらに大きな順序数について記述します。
Bachmann-Howard 順序数は、Kripte-Platek の集合論における証明理論の強さを示すものだとされてい
ます。そして、それよりも強い集合理論を用いて、その限界を示す順序数が定義されるようです。たとえ
ば、second-order arithmetic や Zermelo-Fraenkel がそれに当たります。このような、弱い理論では再帰的
に計算出来ないような大きさの、大きな帰納的順序数が存在するとされています。
4 Ordinal
collapsing function https://en.wikipedia.org/wiki/Ordinal collapsing function
- Large countable ordinal https://en.wikipedia.org/wiki/Large countable ordinal
5 Wikipedia
7.6. Taranovsky の順序数記法
77
そして、そのような弱い理論では再帰できないような帰納的順序数をさらに越えると、いかようにしても
帰納的に定義できない最初の順序数 チャーチ・クリーン順序数 (Church-Kleene ordinal)
6 7
ωCK
が定
1
義されます。これは、最初の帰納的でない順序数です。それでも、ωCK
以下の順序数は可算無限（アレフ
1
0）であり、最初の不可算順序数（濃度がアレフ 0 よりも大きい順序数）である ω1 には到達していません。
つまり、ωCK
< ω1 ですが、実際には多くの場合に ωCK
は ω1 と同じように振る舞うとされています。
1
1
不可算順序数については、 巨大基数 (large cardinal)
8
の理論で研究がされています。この理論が巨大
な自然数を追求する巨大数論にどのように寄与するかは不明なので、本書で取り扱う範囲は可算順序数の
範囲です。ただし、Bachmann-Howard 順序数の定義で示したように、帰納的順序数を定義する目的で、不
可算順序数が用いられることはあります。
7.6
Taranovsky の順序数記法
Dmyto Taranovsky が、大きな順序数の記法を定義9 しています。この文章によれば、順序数記法を以下
の様に定義できます。
1. A General Notation
2. An Ordinal Notation
3. A Stronger Ordinal Notation
4. Second Order Arithmetic
5. Beyond Second Order Arithmetic
最初の An Ordinal Notation の段階で、Veblen 関数、Bachmann-Howard ordinal、proof-theoretical
ordinal、Transfinite Recursion、Monotonic Induction の段階まで記述でき、さらにその先まで記述できる
ようになります。
Taranovsky の順序数記法は、定義を読んでも集合論をしっかりと学んでいない著者には難しくて理解出来
ないので、本書では深入りしません。巨大数探索スレッドの 9 では、この順序数記法の An Ordinal Notation
10
、A Stronger Ordinal Notation
11
、A Step towards Second Order Arithmetic
12
で表される順序数の
収束列と、収束列を求めるために必要な性質がまとめられています。
7.7
多変数 C0
Taranovsky の順序数記法を元に、たろう氏が作成した順序数から順序数への多変数関数 C0 を作成しま
した13 。「0 とこの関数だけで、ψ (Ωω ) 未満のすべての順序数を作ることが出来る」とのことです。さら
に、２重リスト C0 、多変数 C1 などが定義されています。
6 Wikipedia
- Church-Kleene ordinal https://en.wikipedia.org/wiki/Church-Kleene ordinal
Wiki - Church-Kleene ordinal http://googology.wikia.com/wiki/Church-Kleene ordinal
8 Wikipedia - Large cardinal https://en.wikipedia.org/wiki/Large cardinal
9 Ordinal Notation (Dmytro Taranovsky) http://web.mit.edu/dmytro/www/other/OrdinalNotation.htm
10 巨大数探索スレッド 9 の 94 にアップされた文書 (2010 年 12 月 15 日) http://gyafun.jp/ln/archive/9-94.txt
11 巨大数探索スレッド 9 の 97 にアップされた文書 (2010 年 12 月 17 日) http://gyafun.jp/ln/archive/9-97.txt
12 巨大数探索スレッド 9 の 102 にアップされた文書 (2010 年 12 月 17 日) http://gyafun.jp/ln/archive/9-102.txt
13 巨大数探索スレッド 7 の 571 でアップされた文書 (たろう, 2007 年 10 月 17 日) http://gyafun.jp/ln/archive/7-571.txt
7 Googology
第7章
78
帰納関数
【定義】多変数 C0
□ : 0 個以上の 0
Ｘ : 0 個以上の 0 以上の順序数
a, b : 順序数
B : 極限順序数（Bn : 収束列）
として、
C0 (□, a) = a + 1
C0 (Ｘ, b + 1, a) = lim 初項 a / ２項目以降 C0 (Ｘ, b, １個前の項)
C0 (Ｘ, b + 1, 0, □, a) = lim 初項 0 / ２項目以降 C0 (Ｘ, b, １個前の項, □, a)
C0 (Ｘ, B, □, a) = limC0 (Ｘ, Bn , □, a)
大きさは、以下の様に計算されています。
C0 (a, 0) = ωa
C0 (1, 0, 0) = ε0
C0 (2, 0, 0) = η0
C0 (a, 0, 0) = φa (0)
C0 (1, 0, 0, 0) = Γ0 = ψ (0)
C0 (1, 0, a, 0) = Γωa
C0 (1, 1, 0, 0) = ΓΓ...Γ0 = ψ (Ω)
C0 (1, a, 0, 0) = ψ (Ω・a)
C0 (2, 0, 0, 0) = ψ (Ω2 )
C0 (2, 1, 0, 0) = ψ (Ω2 + Ω)
C0 (2, 2, 0, 0) = ψ (Ω2 + Ω・2)
C0 (2, 3, 0, 0) = ψ (Ω2 + Ω・3)
C0 (2, a, 0, 0) = ψ (Ω2 + Ω・a)
C0 (3, 0, 0, 0) = ψ (Ω2・2)
C0 (4, 0, 0, 0) = ψ (Ω2・3)
C0 (ω, 0, 0, 0) = ψ (Ω2・ω)
C0 (1, 0, 0, 0, 0) = ψ (Ω3 )
C0 (1, 0, 0, 0, 0, 0) = ψ (Ω4 )
C0 (1, 0, 0, 0, 0, 0, 0) = ψ (Ω5 )
limC0 (1 が n 個) = ψ (Ωω )
7.8
バード数
バード氏は、ε0 に相当する多重リスト表記を作成した後に、さらにそれよりも大きい関数を作成し、順
序数で評価しています14 。Googology Wiki によれば、
Bird’s H(n) function = f θ (Ω+1)(n)
Bird’s S(n) function = f θ (θ 1(Ω))(n)
Bird’s U(n) function = f θ (Ωω)(n)
14 再掲:
Chris Bird’s Super Huge Numbers http://mrob.com/users/chrisb/
7.9. ミーミーミーロッカプーワ・ウンパ
79
Bird’s array notation = f θ (Ωω)(n) (limit)
となります。その計算は、バード氏自身が丹念に説明をしていますが、著者が Γ0 を超える順序数の理解
がおぼつかないため、ここではそのような評価がされているということを記すに止めておきます。この限
界が、新しい バード数 になります。たろう氏の多変数 C0 でも、ψ (Ωω ) という順序数が限界になってい
て、バード氏の限界と同じ程度になっているので、おそらくここまでが基本列で定義された順序数と対応す
る関数のこれまでの限界ではないかと思います。いずれまた、著者が検証能力を持ったときに、検証をした
いところです。
なお、バード氏の順序数の解析15 によれば、ヴェブレン階層は φ (α, β) = ω↑1+α (ω (1 + β)) とな
るようです。αとβが無限順序数であれば 1+α=α, 1+β=βとなるので、ここではαとβは自然数だと
思います。このヴェブレン階層の計算がまだ理解できていません。
7.9
ミーミーミーロッカプーワ・ウンパ
アメリカのグーゴロジスト、ジョナサン・バウワーズ氏16 は、Googology Wiki によれば17 「現代巨大
数論の父」(the father of modern googology) と呼ばれています。彼は、バード氏や John Spencer 氏の助
けを借りて、巨大数を表記する BEAF
18
という手法を考えました。Googology Wiki では、様々な関数が
BEAF 表記によって大小比較されています。彼は、非常に多くの巨大数の名前をつけました。その中の 1 つ
が、本書で紹介したトリトリです。
彼が考えた最大の数は ミーミーミーロッカプーワ・ウンパ (meameamealokkapoowa oompa)
20
まだ解読出来ていませんが、Googology Wiki によれば
19
です。
F [Γ0 ] を超えたどこかにいるそうなので、新バー
ド数といっしょにこの章に記しておきます。
7.10
その他の関数
巨大数探索スレッド 8 で定義がアップされたナゴヤ関数 Ver1
21
は、Hardy 関数の引数を順序数のリス
トに拡張することと、対角化を使った拡張を基本的なアイディアとしています。
また、ルート 41 氏が巨大数探索スレッド 8
22
でアルカ数、マダ・アルカ数、マダ・アルカオメガ、マ
ダ・アルカグラハム数、アス・アルカオメガ等、色々な巨大数を考えています。
7.11
帰納関数の大きさ比較
15 Beyond
Nested Arrays I http://mrob.com/users/chrisb/Beyond Nested Arrays I.pdf
Home Page http://www.polytope.net/hedrondude/home.htm
17 Googology Wiki - Jonathan Bowers http://googology.wikia.com/wiki/Jonathan Bowers
18 Googology Wiki - BEAF http://googology.wikia.com/wiki/BEAF
19 Infinity Scrapers http://www.polytope.net/hedrondude/scrapers.htm
20 Meameamealokkapoowa oompa http://googology.wikia.com/wiki/Meameamealokkapoowa oompa
21 ナゴヤ関数 Ver1 の定義 (巨大数探索スレッド 8 の 92 でアップされたテキスト) http://gyafun.jp/ln/archive/8-92.txt
22 ログ速 - 巨大数探索スレッド 8 http://www.logsoku.com/r/math/1194777915/
16 Hedrondude’s
第7章
80
帰納関数
表 7.1: 帰納関数の大きさ比較
Hardy 関数
相当する関数
F[ω]
F [ω 2 ]
Knuth の上矢印 3(↑ n)3
n 個の n からなる Conway のチェーン, F3 の s(3) 変換
F [ω 3 ]
F [ω ω ]
チェーンの回転↑ n(3, 3, 3), F3 の s(4) 変換
ωω
多変数アッカーマン, F3 の ss(1)
F [ω ]
F [ε0 ] = F [C0 (1, 0, 0)]
2 重リストアッカーマン, F5 の m(5)
グッドスタイン関数, 多重リストアッカーマン, バードの多重リスト表記, F5 (x)
F [η0 ] = F [C0 (2, 0, 0)]
F [Γ0 ] = F [C0 (1, 0, 0, 0)]
F [limC0 (1 が n 個)] = ψ (Ωω )
F6 (x)
C0 の限界や新バード数?
81
第 8 章 計算不可能な関数
8.1
ビジービーバー関数
本章では、計算不可能な関数について扱います。計算不可能な関数によって作られる数は、計算ができま
せん。 ビジービーバー関数 (Busy beaver function)
1 2 3
は、計算不可能関数の有名な例です。1962 年に
Tibor Rado が論文で n 個の動作状態を持つチューリングマシン (n-state Turing machine) のビジービー
バーゲームを考えて発表しました。
次のような チューリングマシン (Turing machine) 4 を考えます。
• マシンは n 個の動作状態と、停止状態を持つ。ここで、n は正の整数で、その中の 1 つが初期状態で
ある。
• マシンは 1 つの 2 方向の無限に長いテープを使う。
• テープには 2 種類の記号 (0 または 1) が書かれている。
• マシンには遷移関数があり、入力は (1) マシンの現在の状態と、(2) 現在の位置のテープの状態の 2 つ
である。
• 遷移関数は、3 つの出力を持つ。(1) テープの現在の位置から読み出された記号を上書きする記号 (2)
テープ上を動く方向（左または右）(3) 遷移先の状態（停止する場合もある）
チューリングマシンは、プログラムを入力 2 つと出力 3 つの 5 つ組の情報、つまり（現状態、現記号、次
に書く記号、移動方向、次の状態）を有限個並べた表として書けるようなマシンです。
ビジービーバーゲームは、すべて 0 のテープの初期状態から開始して、遷移関数を停止状態になるまで
繰り返します。もし、マシンが最終的に停止したときには、その時のテープ上の 1 の数がマシンのスコアと
なります。n 個の動作状態を持つすべてのチューリングマシンでビジービーバーゲームをしたときに、最大
の値を返すものが n 個の動作状態におけるビジービーバー (n-state busy beaver) であるとされ、最大かど
うかは分からないけれど、現在のところは最大となっているものが優勝マシンとされます。問題は、現在優
勝マシンとされているものがビジービーバーなのかどうかを、確かめる方法がないことです。それを決定す
るためには、あらゆる n 個の動作状態のチューリングマシンを停止しないことが確定するまで走らせる必
要がありますが、どこまで走らせても停止しないことが確定しない（永遠に停止しないのか、いつかは停止
するのかが、いつまでも分からない）、という 停止性問題 (halting problem) が生じるためです。
ビジービーバー関数 Σ(n) は、n 個の動作状態と 2 つの記号 (0 と 1) を持つあらゆるチューリングマシンの
中で、最大の 1 を書いて停止するものが書く 1 の個数です。これは、明確に定義されますが (well-defined)、
計算可能ではありません。十分に小さい n、すなわち Σ(0) = 0, Σ(1) = 1, Σ(2) = 4, Σ(3) = 6, Σ(4) = 13
1 Mathworld
- Busy Beaver http://mathworld.wolfram.com/BusyBeaver.html
- Busy beaver https://en.wikipedia.org/wiki/Busy beaver
3 Googology Wiki - Rado’s sigma function http://googology.wikia.com/wiki/Rado’s sigma function
4 BeneDict 地球歴史館 - チューリングマシンの原理 http://www.benedict.co.jp/Smalltalk/talk-73.htm
2 Wikipedia
第 8 章 計算不可能な関数
82
までは値が分かっていますが、n > 4 に対しては、正確な値が計算されていません。n=5 の時は、4098 を
返すチューリングマシンが見つかりましたが、まだ停止するかどうか分からないチューリングマシンが残っ
ているので、確定していません。n=6 の時は、3.5 × 1018267 という下限が計算されていますが、これもこ
の値が Σ(6) であるかどうかは分かっていません。
「○文字以内で書ける最大の数」あるいは「○文字以内で書けない最小の数」といった時には、この停止
性問題と同じ問題が発生し、計算不可能関数になります。ただし、その時には「どのような表記法が許され
るか」が明確にされていなければなりません。それが明確になされていないと、
「15 文字以内で書けない最
小の数」が 15 文字で書けてしまう、というような問題も発生します。巨大数探索スレッドでは、与えられ
たプログラミング言語である文字数で書ける最大の数、という関数を考えて、具体的にその最大値を求め
よう、というような話題も出ていました。
さて、チューリングマシンは、具体的に計算ができる計算機ですが、これに計算ができないブラックボッ
クスを追加した 神託機械 (oracle machine)
5
を考えることができます。これは、特定の問題を 1 ステッ
プで決定して値を返す機能がついたもので、その特定の問題は計算不可能なものであっても構いません。こ
の神託機械を使って、ふぃしゅ数バージョン 4 を以下のように定義しました。
8.2
ふぃっしゅ数バージョン 4
【定義】ふぃっしゅ数バージョン 4
[1] 関数 f から関数 g への写像 s’(1) を以下で定める。
関数 f を神託 (oracle) として持つチューリングの神託機械 (oracle machine) を考え、この
マシンによるビジービーバー関数を g とする。すなわち「チューリングマシン＋関数 f」の
マシンｎステートでセット可能な１の数の最大を g(n) とする。
[2] s0 (n)(n > 1) および ss0 (n)(n > 0) を、F3 と同様に定める。すなわち、
s0 (n)f := g; g(x) = [s0 (n − 1)x ]f (x)(n > 1)
ss0 (1)f := g; g(x) = s0 (x)f (x)
ss0 (n)f := g; g(x) = [ss0 (n − 1)x ]f (x)(n > 1)
[3] ふぃっしゅ関数 F4 (x) を以下のように定める。
F4 (x) := ss0 (2)63 f ; f (x) = x + 1
[4] ふぃっしゅ数 F4 := F463 (3) とする。
これは、ふぃっしゅ数バージョン 3 の定義では s(1) は、ある関数から原始帰納で他の関数を返すような
汎関数でした。それに対して、ふぃっしゅ数バージョン 4 の s’(1) は、ある関数 f から、その関数を神託と
して持つような神託機械を想定して、その神託機械によるビジービーバー関数を返すような汎関数です。
ここで、F4 (x) は「ビジービーバー関数を元にして帰納的定義を繰り返す」という関数ではありません。
まず、初期の関数である f(x)=x+1 に対して、s’(1) を施すと、これは神託がないビジービーバー関数その
ものなので、s’(1)f(x) がビジービーバー関数に相当します。次に、この s’(1)f(x) に対して再度 s’(1) を施し
5 Wikipedia
- Oracle machine https://en.wikipedia.org/wiki/Oracle machine
8.3. ビジービーバーのハーディー的拡張
83
た s0 (1)2 f (x) は、
「ビジービーバー関数を神託として持つ神託機械」によって計算できない関数なので、ビ
ジービーバー関数から帰納的に定義できるどんな関数よりも大きな関数になります。そのような定義をひた
すら対角化した結果得られる関数が F4 (x) です。
ふぃっしゅ数バージョン 4 を作ったときには、バージョン 3 が最新だったためこれを元としましたが、バー
ジョン 5,6 を元としても同じように定義ができ、その方が大きくなります。この拡張は、帰納関数で議論し
たことを、そのまま計算不可能関数に拡張可能であることを示しています。そのことが、次でより明確にな
ります。
8.3
ビジービーバーのハーディー的拡張
たろう氏により、ビジービーバーのハーディー関数的拡張が以下で定義されました。
【定義】ビジービーバーのハーディー関数的拡張
B[0](n)
B[a + 1](n)
= n
= s0 (1)(B[a])(n)
B[A](n) = B[An ](n)
ここで、s’(1) はふぃっしゅ数バージョン 4 の定義と同じ。
この時、F3 (n) ≒ F [ω
ω+1
ω+1
× 63](n) であることから、F4 (n) ≒ B[ω
× 63](n) となります。
すなわち、大きな順序数からハーディー関数を使って大きな計算可能関数を作ったのと同様の手続きで、
大きな帰納的順序数から B[A] を用いて大きな計算不可能関数を作ることができます。前章までの議論をそ
のまま当てはめ、B[Γ0 ] といったような大きな関数を作ることができます。この関数は、計算不可能では
ありますが定義が可能な関数です。
8.4
Xi 関数
Googology Wiki には、Xi 関数 (Xi function)
6
が定義されています。まず、次のような SKI 表現を定義
します。
• I(x)=x
• K(x,y)=x
• S(x,y,z)=x(z,y(z))
たとえば、S(K, S, K(I, S)) を計算してみます。S 式で x=K, y=S, z=K(I,S) を代入すると、K(K(I, S),
S(K(I, S))) となります。次に、K 式で x=I, y=S を代入すると K(I, S) = I となるため、K(K(I, S), S(K(I,
S))) = K(I, S) となります。さらに、K(I, S) = I となります。このように、S(K, S, K(I, S)) という SKI 表
現は最終的に I になりましたが、無限に記述が増加するようなものもあれば、計算が終わるものもあります。
n 個の文字から始める SKI 表現の中で、最大の有限の文字を返すものが返した文字数を Xi 関数 Ξ(n) とし
ます。SKI 表現はチューリングマシンと同じ強度で、Ξ(n) 関数は計算不可能になります。SKI 計算そのも
6 Googology
wiki - Xi function http://googology.wikia.com/wiki/Xi function
第 8 章 計算不可能な関数
84
のはチューリングマシンと同じ程度の強さですが、神託記号 (oracle combinator) Ω (x,y,z) を導入するこ
とで、強くなります。Ω (x,y,z) は、x の計算結果が I になるときには y を、そうでなければ z を返します。
8.5
ラヨ数
Googology Wiki には、 ラヨ数 (Rayo’s number)
哲学者 Agustin Rayo
8
7
が定義されています。2007 年 1 月 26 日に、MIT の
とプリンストン大学の哲学者 Adam Elga
9
の間で巨大数対決が行われました10 。
そこでラヨ氏が提起したものが、この数です。ラヨ氏の言葉では、このように定義されました。
【定義】ラヨ数
First order の集合論の言葉でグーゴル個以内の記号で表現できるいかなる有限の正の整数よりも大き
な最小の正の整数
「グーゴル」のところを正の整数 n とすれば、急速に増加する ラヨ関数 (Rayo function) Rayo(n) を定
義できます。この計算は、チューリングマシンでも、神託機械でも、n 次のチューリングマシンでも計算で
きない、とされています。集合論による正確な定義は、Googology wiki に書かれています。ここでは、だ
いたいの雰囲気を説明します。
無限に連続するオブジェクト (object) の並びを定義することを変数設定 (variable assignment) としま
す。たとえば、(3,2,6,1/2,4, π,Canada, ω,65,…) のようなもので、Canada が入っているように、オブジェ
クトは数字である必要はありません。なんでも入ります。次に、変数設定に対して適用する式 (formula) を
考えます。この式は、
• ”a ∈ b” a 番目のオブジェクトは b 番目のオブジェクトの要素である
• ”a=b” a 番目のオブジェクトは b 番目のオブジェクトと等しい
• ”(￢ e)” 式 e の否定
• ”(e ∧ f)” 式 e と式 f の論理積 (and)
• ”∃ a(e)” 式 e が真となるように a 番目のオブジェクトを変えることができる
以上 5 つにより構成されます。さて、ある数 m がある式φによって命名可能であるとは、式φを満たすす
べての変数設定に対して、最初のオブジェクトが必ず m となること、そしてそのような変数設定が少なく
とも 1 つは可能であることを言います。ラヨ関数 Rayo(n) は、n 文字以内の式で命名可能ないかなる有限
の正の整数よりも大きな最小の正の整数です。集合論では、自然数を 0 = {}（空集合）、1 = {{}}、のよう
に考えます。そこで、0 を定義するには ”(￢∃ 2(2 ∈ 1))”と定義します。これは、「2 つ目の変数が 1 つ目
の変数の要素であるように、2 つ目の変数を設定することはできない」ことを意味するので「1 つ目の変数
には要素はない」となり、1 つ目の変数は空集合=0 となります。この方法で 1 を定義すると”(((￢∃ 3(3 ∈
2)) ∧ 2 ∈ 1) ∧ (￢∃ 3((3 ∈ 1 ∧ (￢ 3=2)))))”となります。1 を定義するために 38 文字も使ってしまいま
した。もし、38 文字以内で 1 よりも大きな数字を定義する方法がなければ、Rayo(38)=2 ということにな
ります。これまでの急速増加関数と比べると、あまりにも増加率が低いように見えます。しかし、文字数が
増えれば、帰納的に大きな数を表現できるようになり、爆発的に増加するとされています。
7 Googology
wiki - Rayo’s number http://googology.wikia.com/wiki/Rayo’s number
Rayo http://web.mit.edu/arayo/www/
9 Adam Elga http://www.princeton.edu/˜adame/
10 Big Number Duel http://web.mit.edu/arayo/www/bignums.html
8 Agustin
8.5. ラヨ数
85
当初は、ラヨ数は F [ωCK
] 程度の増加だと思われていましたが、それは誤りだということになりました。
ω
n 文字の First-order arithmetic で表現できる数であれば、F [ωCK
] 程度の増加になるようなのですが、そ
ω
れよりも Second-order arithmetic 11 の方が強く、さらに First order set theory は強いから、ということ
です。
ラヨ関数が急速に増加することについて、具体的な計算が無いのでなかなかそのすごさは実感できませ
んが、ラヨ数は Googology Wiki における最大の自然数で、これまでに本書で登場したどのような巨大数よ
りも大きくなるはずなので、得体の知れない大きな自然数です。一見弱そうだけれど実は最強、ということ
です。
チューリングマシンに神託を組み込んでも、ラヨ関数にはかなわないとなれば、ラヨ関数をさらに強め
るためには、ラヨ関数そのものに神託を組み入れるしかありません。そこで、組み入れてみます。
【定義】ラヨ関数のハーディー関数的拡張
関数 f に対して「f(a)=b; a 番目のオブジェクトと b 番目のオブジェクトに対して f(a)=b が成り立つ」
という神託式 (oracle formula) を使用可能な式に加えた時のラヨ関数 g を考え、f を g に変換する汎関
数を RR とする。順序数αに対するラヨ階層をこのように定義する。
R[0](n) =
R[a + 1](n) =
n
RR(R[a])(n)
R[A](n) = R[An ](n)
もしこの定義が矛盾なく可能であれば、この時の R[α] のαに大きな基本列を定義出来る帰納的順序数
を入れれば、非常に大きなラヨラヨ関数、そしてラヨラヨ数ができることでしょう。そこで、ふぃっしゅ数
バージョン 6 の定義で m(0, 2) = RR として R[η0 ] の大きさにした関数を F7 (x) とします。
この時、 ふぃっしゅ数バージョン 7 を F7 := F763 (10100 ) とします。これは大きいと思います。
11 Wikipedia
- Second-order arithmetic https://en.wikipedia.org/wiki/Second-order arithmetic