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

宇宙の談話領域 マーク・ドミヌス (陶敏修) mjd@pobox.com 私について RSS Atom 最近のエントリ 12件 イプシロンゼロへの道：ニムは必ず終わる、無限順序数であっても イプシロンゼロへの道：順序数をニムの山として イプシロンゼロを理解し始める それは私たちの言語だ！ 私は1913年のロードレイジ事件に命を救われた バスマラの解読 1992年の私のコンピュータープログラミングの問題に関する1992年の見解 エジプト分数乗算 更新：サグラダ・ファミリアにいます 2/105 のエジプト分数 アハメスは 2/n の最良の展開を見つけたか？ プログラマーはクロードのために文書化するが、お互いのために文書化しない アーカイブ： 2026: JFMAMJ J 2025: JFMAMJ JASOND 2024: JFMAMJ JASOND 2023: JFMAMJ JASOND 2022: JFMAMJ JASOND 2021: JFMAMJ JASOND 2020: JFMAMJ JASOND 2019: JFMAMJ JASOND 2018: JFMAMJ JASOND 2017: JFMAMJ JASOND 2016: JFMAMJ JASOND 2015: JFMAMJ JASOND 2014: JFMAMJ JASOND 2013: JFMAMJ JASOND 2012: JFMAMJ JASOND 2011: JFMAMJ JASOND 2010: JFMAMJ JASOND 2009: JFMAMJ JASOND 2008: JFMAMJ JASOND 2007: JFMAMJ JASOND 2006: JFMAMJ JASOND 2005: OND サブトピック： 数学 251 プログラミング 102 言語 97 その他 75 書籍 50 技術 49 語源 36 Haskell 33 おっと 30 Unix 27 宇宙の呼び声 25 Math SE 25 法律 23 物理学 21 Perl 17 生物学 16 脳 15 カレンダー 15 食べ物 15 コメントは無効です 日曜日、2026年7月19日 イプシロンゼロへの道：ニムは必ず終わる、無限順序数であっても 以前：順序数と基本的な集合論 順序数をニムの山として 昨日、私はゲーム「ニム」について話しました。これは2人のプレイヤーがいくつかの山から豆を取り合うゲームで、緑のトークンを含む拡張版では、それらは無限の山のように振る舞います：1つ以上の緑のトークンがある山がある場合、プレイヤーはそれらをすべてまたは一部を取り除き、その後、その山に任意の数の豆を追加することが合法です。 最初は、!!ω!!トークンを含むニムは永遠に続くように思えるかもしれません。そうではありません！もし誰かがあなたに豆がすべて入った山を持つニムの位置を与えたら、ゲームがどれくらい続くか事前に言うことができます。ニムの山が!!{1, 3, 4, 8}!!で始まるゲームは、16ターン以上続くことはありません。なぜなら、各ターンは少なくとも1つの豆を山から取り除き、誰かが最後の豆を取ったときにゲームは終了するからです。 ゲームがニムの山が!!{1, 3, 4, 8, ω}!!で始まる場合、どれくらい続くかを知ることはできません。もし1,000ターンで終わると推測した場合、最初のプレイヤーは!!ω!!トークンを10,000個の豆の山に置き換えることで、あなたの推測を間違っていると証明することができます。そして、ゲームはさらに最大10,016ターン続くかもしれません。もしあなたが最初にゲームが最大10,016ターン続くと推測した場合、プレイヤーの1人はトークンを1,000,000,000,000,000,000個の豆の山、あるいはそれ以上に置き換えるかもしれません。最初の移動の前には、ゲームが終了するまでの期間に制限を設けることはできません。 しかし、!!{1, 3, 4, 8, ω}!!について言えることは、最大17回の移動の後、誰かが!!ω!!トークンを取り除き、それを有限数の豆に置き換えるということです。そしてその時点で、ゲームがいつ終わるかを知ることができるようになります。 !!ω·2!! 同様に、山が!!{1, 3, 4, 8, ω·2}!!であると仮定します。!!ω·2!!は単に2つの緑のトークンのスタックであることを思い出してください。このゲームはどれくらい長く続く可能性がありますか？前述のように、言うことはできません。しかし、最大17回の移動の後、少なくとも1つの!!ω!!トークンが取り除かれ、最大で1つの!!ω!!トークンと、おそらく非常に多くの豆（例えば!!b_1!!）が残ることを言うことができます。そして、最大!!b_1+1!!回の移動の後、最後の!!ω!!トークンが（そうでなければ）取られ、豆だけが残るでしょう。おそらく非常に多くの豆（例えば!!b_2!!）が残るでしょう。そしてその時点で、ゲームがそれ以上!!b_2!!回以上続くことはないことを確信できるでしょう。 したがって、!!{1, 3, 4, 8, ω·2}!!では、ゲームがいつ終わるかを知ることはできません。また、ゲームがいつ終わるかを知ることができるようになるのがいつかを知ることもできません。しかし、最大17回の移動で、ゲームがいつ終わるかを知るのではなく、ゲームが終わる時期を知ることができるようになる時期を知ることができるようになることを言うことができます。 プログラミングタスクの見積もり これは、私がかつて別のプログラマーから聞いた話に似ています。彼は、上司がバグを修正できるかどうか尋ねに来たと言いました。彼はできると答え、上司はどれくらいかかると思うか尋ねました。彼は「わかりません、考えなければなりません」と言いました。彼のボスは、合理的な女性だったので、「いつ教えてくれるのですか？」と尋ねました。彼は再び「わかりません、考えなければなりません」と言いました。 この男と以前から付き合いのあるボスは、怒りを失いませんでした。代わりに、彼女は彼にそれを理解するのにどれくらい時間がかかるか尋ねました。「2日以上はかかりません」と彼はすぐに言いました。「わかりました」と彼女は言いました。「誤解がないことを確認するためですが、2日後でも見積もりができないかもしれませんが、いつ見積もりが準備できるか教えてくれるということですか？」「その通りです。」そして、両者は満足して友好的に別れました、少なくともその時は。 経営陣とエンジニアリング部門とのコミュニケーションは、必ずしもそううまくいくとは限りません！ 私の友人は明らかに!!ω·2+1!!というゲームをプレイしていました。豆は1つしかなく、2日目までには!!ω!!トークンの1つがなくなっていなければなりませんでした。その時点で!!ω + n!!（有限数!!n!!）が残るでしょう。そして、私の友人はその時点でゲームがどれくらい続くか言えないかもしれませんが、彼はさらに!!n+1!!日以内に見積もりを提出できることを知るでしょう。 ゲームは終わらなければならない！ !!ω·2+1!!では、ゲームがいつ終わるか、またはゲームが終わる時期を知ることができるようになるのがいつかを知ることはできません。しかし、最大2回の移動で、ゲームが終わる時期を知ることができるようになる時期を知ることができるようになることを知ることができる、ということは、ゲームが終わる時期を知ることができるようになる時期を知ることができるようになる時期を知ることができるようになる、ということになります。そしてそれは、ゲームが終わることを知っているということになります。たとえそれがいつ起こるかについてはかなり遠いとしてもです。 議論は常に同じです：豆の数は有限であり、両方のプレイヤーがトークンを避けようとしても、豆はやがてなくなり、誰かが緑のトークンをより多くの豆に置き換えることを余儀なくされます。そして、それらの豆がなくなり、誰かが別のトークンを取ることを余儀なくされ、そしてそうこうしているうちに、すべてのトークンがなくなり、そして豆がなくなったときにゲームは終了します。もちろん、トークンと豆の両方がそれよりも速くなくなるかもしれません。しかし、それらは、どれほど遅く、たとえ一度に1つずつであっても、進んでいきます。そしてこれは、最初にどれだけの緑の!!ω!!トークンがあったとしても当てはまります。そして、平方数!!ω^2!!トークンがあったとしても、同じことが当てはまります。プレイヤーが平方トークンを避けたとしても、いつかすべての豆と緑の!!ω!!トークンが使い果たされ、誰かが少なくとも1つの平方!!ω^2!!トークンをより多くの豆と緑のトークンに置き換えることを余儀なくされ、そしてそれらが使い果たされ…そして最終的に最後の平方!!ω^2!!トークンがなくなり、そして私たちは前の段落の!!ω·n+m!!ケースに戻り、ゲームは終了しなければなりません。 しかし、その時点で私たちは英語の説明を打ち負かしました。私たちは「ゲームが終わるまでの時間を知るまでの時間を知るまでの時間を知る…」という無限のシーケンスを積み上げてきました。「ゲームが終わるまでの時間を知るまでの時間を知る…」という時間を知ることはできません。 奇妙だ！ それでも、これらのゲームでさえ終わらなければならないことを私たちは知っています。たとえ英語が、どれくらい時間がかかるか、あるいはどれくらい時間がかかるかを知ることができるようになるまでの時間を言うのに十分なほど強力でなくてもです。 順序数は整礎である 順序数とは、より小さな順序数の集合です。ニムの各手は順序数を小さくします。数を小さくし続けると、最終的に0に到達し、ゲームは終了します。順序数のこの性質は整礎性と呼ばれます。順序数は整礎であると言います。 これは順序数の特別な性質であり、すべての種類の数に共有されるものではないことに注意してください。例えば、正の有理数はこの性質を持ちません。!!1!!から、より小さな!!rac12!!、次にさらに小さな!!rac13!!へと下っていくことができます。そして、常に下へ、より小さく、より小さい数へと下っていきますが、n