Mark Jason Dominus：通往 ε₀ 之路：Nim 游戏总是会结束，即使使用无限序数

通往 ε₀ 之路：Nim 游戏总是会结束，即使使用无限序数

之前：

1. 序数与基础集合论
2. 序数作为 Nim 堆

昨天 我讨论了 Nim 游戏，涉及两名玩家从若干堆中取豆子，以及一种包含绿色代币的扩展版本，这些代币的行为有点像无限堆：

当某堆中有一个或多个绿色代币时，玩家可以合法地移除任意数量的代币，然后向该堆添加 任意 数量的豆子。

乍看起来，带有 !!ω!! 代币的 Nim 游戏似乎可以永远进行下去。事实并非如此！

如果有人给你一个所有堆都包含豆子的 Nim 局面，你可以提前说出游戏可能持续多长时间。以 nim 堆大小为 !!\{1, 3, 4, 8\}!! 的游戏开局，绝对不可能持续超过 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 堆的方法。

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