Mark Jason Dominus：通往 ε₀ 之路：即使使用無限序數，Nim 遊戲也會結束

通往 ε₀ 之路：即使使用無限序數，Nim 遊戲也會結束

先前文章：

1. 序數與基礎集合論
2. 將序數視為 Nim 堆

昨天 我談到了 Nim 遊戲，遊戲中兩位玩家從數個堆中拿取豆子，以及一種延伸版本，其中包含綠色代幣，行為有點像無限堆：

當某堆有一個或多個綠色代幣時，玩家可以合法地移除其中任意數量，然後再往該堆中加入任意數量的豆子。

乍看之下，帶有 !!ω!! 代幣的 Nim 遊戲似乎可以永遠進行下去。其實不然！

如果有人給你一個所有堆都只含豆子的 Nim 局面，你可以事先預測這場遊戲可能持續多久。從大小為 !!\{1, 3, 4, 8\}!! 的 Nim 堆開始的遊戲，絕對不可能持續超過 16 回合，因為每回合至少會從某一堆中拿走一顆豆子，而當有人拿走最後一顆豆子時遊戲便結束。

如果遊戲開始時的 Nim 堆大小為 !!\{1, 3, 4, 8, \omega\}!!，你就無法知道它可能持續多久。如果你猜測它會在 !!1,\!000!! 回合內結束，第一位玩家可能會用 !!10,\!000!! 顆豆子取代 !!\omega!! 代幣，證明你的猜測是錯的，之後遊戲可能再持續最多 !!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!! 只是兩個綠色代幣堆疊在一起。這個遊戲最長可能持續多久？

和之前一樣，我們無法說出確切時間。但我們可以說：在最多 !!17!! 回合之後，至少其中一個 !!ω!! 代幣會被移除，接著最多只剩一個 !!ω!! 代幣，以及可能非常大量的豆子（假設為 !!b_1!!）。之後再經過最多 !!b_1+1!! 步，如果之前還沒移除，最後一個 !!ω!! 代幣就會被拿走，只剩下豆子，可能數量非常龐大（假設為 !!b_2!!）。

而到了那個時點，我們就能確定遊戲不可能再持續超過 !!b_2!! 步。

因此，對於 !!\{1, 3, 4, 8, \omega·2\}!!，我們無法說出遊戲何時結束。

我們也無法說出「我們何時能夠說出遊戲何時結束」。

但是我們可以說：在最多 !!17!! 步之後，我們將能夠說出（不是遊戲何時結束，而是）我們何時能夠說出遊戲何時結束。

估算程式設計任務

這讓我想起曾經從另一位程式設計師那裡聽來的故事。他說他的老闆來問他是否能修復某個 bug。他回答可以，老闆便問他認為需要多久。

他說：「我不知道，我得先想一想。」

他的老闆是個通情達理的女性，便問他何時才能告訴她答案。

他還是說：「我不知道，我得先想一想。」

老闆之前已經跟這位工程師打過交道，因此並沒有發脾氣。她轉而問他需要多久才能想出答案。

「最多兩天。」他立刻回答。

「好，」她說。「為了確保沒有誤解，請問你是在告訴我，兩天之後你可能還無法估算這個任務，但你會告訴我何時能提供估算嗎？」

「沒錯。」

雙方和氣地結束對話，至少當時雙方都感到滿意。管理階層與工程團隊之間的溝通，並非總是如此順利！

我的朋友當時顯然是在玩 !!ω·2+1!! 這場遊戲。只有一顆豆子，所以在第二天之前，其中一個 !!ω!! 代幣必定會被移除。此時剩餘的局面會是 !!ω + n!!（其中 !!n!! 為某個有限數），雖然我的朋友在那個時點無法說出遊戲會持續多久，但他確實知道自己最多再過 !!n+1!! 天就能提供估算。

遊戲必定會結束！

對於 !!ω·2+1!!，我們不知道遊戲何時結束，也不知道我們何時才能知道遊戲何時結束。

但是我們確實知道：在最多兩步之後，我們將知道「我們何時才能知道遊戲何時結束」，這表示我們確實知道那場遊戲會結束，即使我們還遠遠無法說出它何時結束。

論證始終如一：豆子的數量是有限的，如果沒有人拿走代幣，豆子終將用盡，迫使某人必須用更多豆子取代綠色代幣。接著那些豆子也會用盡，迫使某人再拿走另一個代幣，依此類推，直到所有代幣都被拿走，之後當豆子用盡時，遊戲便結束。

當然，代幣與豆子可能比這個速度更快地被拿走。但無論多慢，即使一次只拿一個，它們還是會被拿走。

無論一開始有多少個綠色 !!ω!! 代幣，這都是事實。

同樣地，如果有任何平方 !!ω^2!! 代幣也成立。在某一時刻，所有豆子與綠色 !!ω!! 代幣都會被用盡，迫使某人必須用更多豆子與綠色代幣取代至少一個平方 !!ω^2!! 代幣，接著那些東西也會被用盡……直到最後一個平方 !!ω^2!! 代幣消失，此時我們就回到前一段所述的 !!ω·n+m!! 情況，而遊戲必定會結束。

但到了這個階段，我們已經超越了英文描述的能力。我們將無數個「我們何時才能說出」的序列堆疊成「我們無法說出我們何時才能說出……遊戲何時結束」。

這很奇妙！然而我們知道即使是這些遊戲也必定會結束，儘管英文無法有力地描述它需要多久，或者甚至無法描述我們何時才能說出它需要多久。

序數是良基的

一個序數是較小序數的集合。Nim 遊戲中的每一步都會讓一個序數變得更小。如果你不斷讓數字變得更小，你最終會達到 0，此時遊戲便結束。

序數的這個性質稱為良基性。我們說序數是良基的。你可以一直向上攀升到越來越瘋狂的無限序數，但無論你向上走了多遠，你都無法一直向下走下去，你必須在有限的時間內到達零。

良基排序也是遞迴程式的理論基礎。當我們撰寫遞迴函式時，我們希望確定它會終止。這意味著如果函式用不同的引數呼叫自己，新的引數必須比原本的引數更小。「更小」可能指數值上較小，但也可能代表許多其他意義。如果函式正在處理目錄樹，「更小」可能指「層級較淺」。如果函式正在排序清單，「更小」可能指「排序錯誤的項目較少」。遞迴的本質是縮小的過程無法永遠持續。函式最終會達到數字零、只包含檔案的目錄，或是沒有未排序元素的清單，然後它就會完成。

在下一篇文章中，我們將看到一種比各種形狀與顏色的代幣拼湊更統一的方式，來理解無限 Nim 堆。

[/math/ordinals 分類中的其他文章] 永久連結