HN 日本語サマリー

← 一覧へ戻る
科学・技術

イプシロンゼロへの道:無限順序数でもニムは必ず終わる

The road to epsilon-zero: Nim always ends, even with infinite ordinals (blog.plover.com)

11 pointsby pavel_lishin3 コメント

要約

この記事は、数学における順序数とゲーム理論のゲーム「ニム」の関係を探求しています。無限の要素(緑のトークン)を含むニムのゲームでも、特定の条件下では必ず終了することが、順序数の「整礎性」という性質を用いて説明されています。この概念は、プログラミングにおけるタスクの見積もりにも例えられています。

全文翻訳

議論の宇宙

イプシロンゼロへの道:無限順序数でもニムは必ず終わる

前回まで:

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

[昨日][前の記事2つへ]私は、2人のプレイヤーが複数の山から豆を取り合うゲームであるニムと、無限の山のような振る舞いをする緑色のトークンを含むその拡張について話しました。

[画像: 緑色のポーカーチップの画像]

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

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

もし誰かがあなたに、すべての山に豆が入っているニムの状態を与えたら、ゲームがどれくらい続くかを事前に言うことができます。!!{1, 3, 4, 8}!!のニムの山で始まるゲームは、16ターン以上続くことはありません。なぜなら、各ターンで少なくとも1つの豆が山から取り除かれ、誰かが最後の豆を取ったときにゲームは終了するからです。

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

もしゲームが最大10,016ターンで終わると最初に推測した場合、プレイヤーの1人がトークンを1,000,000,000,000,000,000個の豆の山、あるいはそれ以上に置き換える可能性があります。最初の1手より前に、ゲームが終了するまでの期間に上限を設けることはできません。

しかし、!!{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つしかなく、!!ω!!トークンの1つは2日以内に処理されなければなりませんでした。その時点で!!ω + n!!(nは有限数)が残り、友人はその時点でゲームがどれくらい続くか言えなかったとしても、さらに!!n+1!!日以内に見積もりを提出できることはわかっていたでしょう。

ゲームは必ず終わる!

!!ω·2+1!!では、ゲームがいつ終わるか、あるいはゲームが終わる時期を知るまでどれくらいかかるかはわかりません。

しかし、最大2手で、ゲームが終わるまでの期間を知るまでどれくらいかかるかがわかるようになり、それは「ゲームが終わる」ということを知っている、ということになります。たとえそれがいつ起こるかを知るまでには、まだかなり時間がかかるとしてもです。

議論は常に同じです:豆の数は有限であり、両プレイヤーがトークンを避けようとしても、豆はいずれなくなり、誰かが緑色のトークンをより多くの豆に置き換えることを余儀なくされます。そして、それらの豆もなくなると、誰かが別のトークンを取ることを余儀なくされ、そして、最終的に最後の緑色のトークンがなくなると、前の段落の!!ω·n+m!!のケースに戻り、ゲームは終了しなければなりません。

もちろん、トークンも豆ももっと速くなくなるかもしれません。しかし、それらは、たとえゆっくりであっても、たとえ一度に1つずつであっても、必ずなくなっていきます。

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

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

しかし、その時点で私たちは英語の説明能力を超えてしまいます。「ゲームが終わるまでの期間」を言うことができない、という状況が無限に積み重なり、「ゲームが終わるまでの期間を言うことができるようになるまでの期間」を言うことができない、という状態になります。

奇妙です!しかし、これらのゲームでさえ必ず終了することはわかっています。たとえ英語が、それがどれくらい時間がかかるか、あるいはそれがどれくらい時間がかかるかを言えるようになるまでどれくらいかかるかさえ、言うには十分な力を持っていなくてもです。

順序数は整礎である

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

順序数のこの性質は整礎性と呼ばれます。順序数は整礎的であると言います。

これは順序数の特別な性質であり、すべての種類の数に共通するものではないことに注意してください。例えば、正の有理数はこの性質を持ちません。!!1!!から、より小さい!!\frac12!!へ、次にさらに小さい!!\frac13!!へと、下へ下へと、ますます小さくなる数へと進むことができますが、決してゼロには到達しません。豆を無限に小さく割ることができるニムのゲームは、決して終わらないかもしれません。しかし、順序数を用いたニムのゲームは必ず終わります。なぜなら、順序数は整礎的だからです。あなたはどこまでも上へ、ますます奇妙な無限順序数へと進むことができますが、どれだけ上へ進んでも、下へ下へと永遠に進むことはできず、有限時間後に必ずゼロで底を打ちます。

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

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

次に続くもの:

そして:

Claudeが緑色のポーカーチップの画像を生成しました。この記事の他のすべては、完全に私によって書かれました。

[/math/ordinalsカテゴリの他の記事] パーマネントリンク