利用者:Nayuta Ito/巨大数における有限と無限
この記事では、巨大数における有限と無限について解説する。
前提知識
- 知らないと厳しい: 数学的帰納法
- 知ってると便利: ペアノの公理
- 知ってると便利: 公理的集合論
目次
第0章 RPGの塔
無限のモンスターが住まう無限の塔を考える。ただし、この塔はイギリスにあるものとする。
塔の0階には受付の人間がいて、それより上の階には1匹ずつモンスターがいる。モンスターの強さには、以下のような関係があるものとする。
- 全てのモンスターは人間より強い。
- XがYより強く、YがZより強いなら、XはZより強い。すなわち、強さに3すくみのような「ループ」は存在しない。
- 任意のモンスターに対し、そこから「それより弱いモンスターを選ぶ」という操作をいつか繰り返すと、必ずいつかは弱いモンスターがいなくなる。
具体例
つまらない例
上に行くほど強くなる無限の塔を考える。
すなわち、強さの序列が0階<1階<2階<・・・と無限に続いていく。
この塔は上の条件を全て満たしている。3つ目の条件を満たすことを厳密に示すためには数学的帰納法が使用される。
多少は面白い例
偶数階・奇数階ごとに上に行くほど強くなる無限の塔を考える。また、奇数階は上級者向けであり、奇数階のどのモンスターも偶数階の全てのモンスターを一撃で倒せるものとする。
このときの強さの序列は0階<2階<4階<・・・<1階<3階<5階<・・・となり、無限をさらに超えて続いていく。
この塔は上の条件を全て満たしている。3つ目の条件を満たすことを厳密に示すためには数学的帰納法を拡張した超限帰納法と呼ばれる証明法が使用される。
第1章 クエスト
あなたは絶対にオーバーフローしないカウンターを持っている。そのカウンターを持って、ヘリコプターでこの塔に窓から乱入したとする。カウンターの初期値は任意とするが、一般にnという記号が用いられるためこの記事でもそれに従う。
あなたはプレイヤーなのでモンスターに負けることはないとする。
さて、あなたがモンスターを瀕死にまで追い込むと、モンスターはカウンターの値を要求する。
あなたがカウンターを見せると、モンスターは「302 Found......」と断末魔を上げながら倒れ、最期に自分より弱いモンスターがいる階数を1つ提示する。いないときは0階を提示する。
また、カウンターをインクリメントするかしないかのbooleanパラメータ(この記事だけの用語としてインクリメントパラメータと呼ぶ)もあなたに渡される(実際には常にtrueでもいいのだが、巨大数の慣習に合わせてfalseになるケースもサポートしておく)。
このリダイレクトはカウンターの値と現在の階数だけで決まり、時刻や乱数といった外部の要素は用いないものとする。
あなたはモンスターから渡されたパラメータによってカウンターをインクリメントするかしないかし、その階に向かう。
0階に降りるまでこれを繰り返す。
注意: ヘリコプターで乱入した階数をα、カウンターの初期値をnとすると、0階に降りたときのカウンターの値はαとnの関数として表される。この関数をこの記事だけの用語としてこの塔に付随する巨大関数と呼ぶことにする。第1引数がαで第2引数がnである。
シンタックスシュガー
自然数だとこの後の議論が面倒なので、塔の階数は適当なエンコーディングでデコードされた文字列で表示されているものとする。文字列として不適当なバイナリデータ(UTF-8エンコーディングにおける11000000 11000000など)に対応する解には、モンスターの代わりに人間を置いておく。文字列として不適当な階数には今後の議論で行くことはないので、これはさほど問題ではない。
具体例
強さの序列だけではなく、モンスターのリダイレクトも定義しなければならない。
つまらない例
上に行くほど強くなる無限の塔を考える。
すなわち、強さの序列が0階<1階<2階<・・・と無限に続いていく。
a階のモンスターはa-1階にリダイレクトするものとする。(a>=1)
また、インクリメントパラメータは常にtrueであるものとする。
このとき、この塔に付随する巨大関数はf(α,n)=α+nである。このことはαに関する数学的帰納法で示せる。せっかくなので証明しておこう。
証明
(i) α=0のとき: f(0,n)は定義から明らかにnである。0+nは(足し算の定義から示そうとすると)そこまで自明ではないがnである。よって両辺は等しい。
(ii) α=kのときの成立を仮定してα=k+1のとき(k>=0): カウンターがnの状態でk+1階のモンスターを倒すとカウンターがn+1になってk階にリダイレクトされる。よってf(k+1,n)=f(k,n+1)=k+(n+1)である。いっぽう(k+1)+nも足し算の定義からk+(n+1)であるから、両辺は等しい。
(i)(ii)より、f(α,n)=α+nが示された。
多少は面白い例
偶数階・奇数階ごとに上に行くほど強くなる無限の塔を考える。また、奇数階は上級者向けであり、奇数階のどのモンスターも偶数階の全てのモンスターを一撃で倒せるものとする。
このときの強さの序列は0階<2階<4階<・・・<1階<3階<5階<・・・となり、無限をさらに超えて続いていく。
a階のモンスターのリダイレクト規則が以下であるとする (a>=1):
- もしa≠1なら、a-2階にリダイレクトする。
- もしa=1なら、カウンターの値を取得し、それを2倍した数の階にリダイレクトする。
また、インクリメントパラメータはa≠1と同値(i.e. a=1のときfalse、a≠1のときtrue)であるものとする。
リダイレクトした先の方が弱いことは明らかである。
このとき、この塔に付随する巨大関数はf(α,n)=α/2+n (αが偶数のとき)、α-1+2n (αが奇数のとき)である。
当然強いモンスターがいる階から始めるほど関数は大きくなる。αが奇数のときはnの係数に2が付いているが、これはこの塔の構造から来る本質的なものである。
もっと面白い例
塔を偶奇ではなく3で割った余りで分割し、階数を3で割った余りが0なら初心者向け、1なら上級者向け、2ならエンドコンテンツ、という仕様にする。
強さの序列は0階<3階<6階<・・・<1階<4階<7階<・・・<2階<5階<8階<・・・となり、無限の階層が3個積み重なっている。
[ここにリダイレクト規則を挿入]
[ここにインクリメントパラメータの規則を挿入]
[ここに巨大関数の説明を挿入]
[ここにnの係数の説明を挿入]
