Mark Jason Dominus: ε₀への道: 無限順序数を使ってもニムは必ず終了する

ε₀への道: 無限順序数を使ってもニムは必ず終了する

これまでの記事:

1. 順序数と基本集合論
2. ニム山としての順序数

昨日、ニムのゲームについて話しました。複数の山から豆を取る2人プレイヤーのゲームで、緑色のトークンを追加した拡張版も紹介しました。この緑色のトークンは、無限の山のように振る舞います:

1つ以上の緑色トークンがある山では、プレイヤーはそれらを任意の数だけ取り除き、その山に任意の数の豆を追加することが合法となります。

最初は、!!ω!!-トークンを使ったニムが永遠に続くように思えるかもしれません。しかし、そうではありません!

すべての山に豆が入っているニム局面を与えられた場合、ゲームがどれくらい続く可能性があるかを事前に言うことができます。ニム山の大きさが!!\{1, 3, 4, 8\}!!のゲームは、単純に16ターン以上続くことはありません。なぜなら、各ターンは少なくとも1つの豆を山から取り除き、最後の豆を取ったプレイヤーがゲームを終了させるからです。

ニム山の大きさが!!\{1, 3, 4, 8, \omega\}!!のゲームが始まった場合、それがどれくらい続くかはわかりません。!!1,\!000!!ターン以内に終わるだろうと推測しても、最初のプレイヤーが!!\omega!!-トークンを!!10,\!000!!個の豆の山に置き換えることで、あなたの推測を覆す可能性があり、その場合、ゲームは最大で!!10,\!016!!ターン以上続くかもしれません。

ゲームが!!10,\!016!!ターン以内に終わるだろうと最初に推測したとしても、プレイヤーの一人がトークンを!!1,\!000,\!000,\!000,\!000,\!000,\!000!!個の豆の山に置き換える可能性があります。それ以上の数になることもあります。最初の動きの前には、ゲームが終了するまでの時間に上限を設けることはできません。

しかし、!!\{1, 3, 4, 8, \omega\}!!について言えることは、最大で!!17!!手以内に、誰かが!!ω!!-トークンを取り除き、それを有限個の豆に置き換えるということです。そしてその時点で、ゲームがいつ終了するかを言うことができるようになります。

!!ω·2!!

同様に、山が!!\{1, 3, 4, 8, \omega·2\}!!であるとします。!!\omega·2!!は、単に2つの緑色トークンを積み重ねたものです。このゲームは最長でどれくらい続くでしょうか?

前と同様に、それはわかりません。しかし、最大で!!17!!ターン以内に、!!ω!!トークンの少なくとも1つが取り除かれ、!!ω!!トークンが最大1つと、場合によっては非常に多くの豆、例えば!!b_1!!が残ることは言えます。そしてさらに最大で!!b_1+1!!手以内に、最後の!!ω!!トークンが（まだ取り除かれていなければ）取り除かれ、豆だけが残ることになります。残る豆の数は、非常に多くなる可能性があります。!!b_2!!としましょう。

そしてその時点で、ゲームが!!b_2!!手以上続くことはないと確信できます。

したがって!!\{1, 3, 4, 8, \omega·2\}!!では、ゲームがいつ終了するかはわかりません。

また、ゲームがいつ終了するかを言えるようになるのがいつになるかもわかりません。

しかし、最大で!!17!!手以内に、ゲームがいつ終了するかを言うのではなく、ゲームがいつ終了するかを言えるようになるのがいつになるかを言えるようになる、ということは言えます。

プログラミングタスクの見積もり

これは、別のプログラマーから聞いた話に似ています。彼のボスが、あるバグを修正できるかどうかを尋ねてきました。彼は「できます」と答え、ボスは「どれくらいかかりそうか」と尋ねました。

彼は「わかりません、考えてみます」と答えました。

ボスは合理的な女性だったので、「いつになったら教えてくれるの？」と尋ねました。

彼は再び「わかりません、考えてみます」と答えました。

ボスはこの男と以前にやり取りをしたことがあったので、怒りを爆発させませんでした。代わりに、「それを判断するのにどれくらいかかる？」と尋ねました。

「2日以内です」と彼は即座に答えました。

「わかりました」とボスは言いました。「誤解がないように確認させてください。2日後にはタスクの見積もりを出せないかもしれないが、見積もりがいつ出せるかを私に伝えることはできる、という意味ですね？」

「その通りです」

そして二人は和やかに別れました。少なくともその時点では、双方とも満足していました。経営陣とエンジニアリングの間のコミュニケーションが、いつもこううまくいくとは限りません!

私の友人は明らかに!!ω·2+1!!というゲームをしていたようです。豆は1つしかなかったので、2日目までに!!ω!!トークンの1つがなくなっているはずです。その時点で、残りは有限数!!n!!に対する!!ω + n!!となり、友人はその時点でゲームがどれくらい続くかを言うことはできないかもしれませんが、最大でさらに!!n+1!!日後には見積もりを提出できることを知っているでしょう。

ゲームは必ず終了する!

!!ω·2+1!!では、ゲームがいつ終了するかも、ゲームがいつ終了するかを知るのがいつになるかもわかりません。

しかし、最大で2手以内に、ゲームがいつ終了するかを知るのがいつになるかを知ることができることはわかっています。そしてそれは、ゲームが終了することを知っているということです。たとえそれがいつ起こるかを言うところからかなり遠く離れていたとしても。

議論は常に同じです: 豆の数は有限であり、誰もトークンを取らなければ、豆は最終的に使い果たされ、誰かが緑色のトークンをより多くの豆に置き換えることを余儀なくされます。そしてそれらの豆が使い果たされ、誰かが別のトークンを取ることを余儀なくされ、以下同様に、すべてのトークンがなくなるまで続き、その後豆が使い果たされた時点でゲームは終了します。

もちろん、トークンと豆の両方がそれより速くなくなる可能性もあります。しかし、どれほどゆっくりであっても、一度に1つずつであっても、必ずなくなります。

そしてこれは、最初にどれだけの緑色の!!ω!!トークンがあったとしても真です。

また、!!ω^2!!の正方形トークンがあったとしても同じことが成り立ちます。ある時点で、すべての豆と緑色の!!ω!!トークンが使い果たされ、誰かが少なくとも1つの!!ω^2!!の正方形トークンを、より多くの豆と緑色のトークンに置き換えることを余儀なくされます。そしてそれらは使い果たされ... 最終的に最後の!!ω^2!!の正方形トークンがなくなり、その時点で前の段落の!!ω·n+m!!の場合に戻り、ゲームは終了しなければなりません。

しかし、その時点で、私たちは英語による記述を打ち負かしています。「ゲームが終了する前にどれくらいで言えるようになるか」を、「ゲームが終了する前にどれくらいで言えるようになるかを言えるようになる前にどれくらいで...」という無限の連鎖に積み重ねてきました。

奇妙です! しかし、私たちはこれらのゲームでさえ終了しなければならないことを知っています。英語には、それがどれくらいかかるか、またはそれがどれくらいかかるかを言えるようになるのがいつになるかを言うのに十分な力がないのです。

順序数は整礎である

順序数はより小さい順序数の集合です。ニムの各手は順序数をより小さくします。もし数をより小さくし続けると、最終的に0に到達し、ゲームは終了します。

この順序数の性質は整礎性と呼ばれます。私たちは順序数が整礎であると言います。あなたは狂ったような無限の順序数へと永遠に上り続けることができますが、どれだけ上へ行っても、下へ下へと永遠に続けることはできず、有限の時間後に必ず0で底を打たなければなりません。

整礎順序は、再帰プログラムの理論的基盤でもあります。再帰関数を書くとき、それが確実に終了することを望みます。そしてそれは、関数が自分自身を異なる引数で呼び出す場合、新しい引数が以前よりも小さいことを意味します。「小さい」は、数値的に小さいことを意味するかもしれません。しかし、それは他の多くのことを意味する可能性があります。関数がディレクトリツリーを処理している場合、「小さい」は「それほど深くないレベルである」ことを意味するかもしれません。関数がリストをソートしている場合、「小さい」は「順序が乱れている要素が少ない」ことを意味するかもしれません。再帰の本質は、縮小が永遠に続くことはできないということです。関数は最終的に数0、またはファイルのみを含むディレクトリ、またはソートされていない要素のないリストに到達し、その時点で終了します。

次の記事では、無限のニム山を、さまざまな形や色のトークンの寄せ集めとしてではなく、より統一された方法で理解する方法を見ていきます。

[Other articles in category /math/ordinals] permanent link