通往epsilon-zero之路：Nim总是结束，即使有无限序数

# 通往epsilon-zero之路：即使有无限序数，Nim游戏也终会结束 来源：https://blog.plover.com/math/ordinals/02-wellfoundedness.html 2026年7月19日（周日） ## 通往epsilon\-zero之路：即使有无限序数，Nim游戏也终会结束（https://blog.plover.com/math/ordinals/02-wellfoundedness.html） 往期内容： 1. 序数与基础集合论（https://blog.plover.com/math/epsilon-zero.html） 2. 序数作为nim堆（https://blog.plover.com/math/ordinals/01-nim.html） 昨天（https://blog.plover.com/math/ordinals/01-nim.html）我聊到了Nim游戏——两个玩家从若干堆豆子中取豆，以及一种扩展玩法，其中加入了行为类似于无限堆的绿色代币： > 当有一堆中有一枚或多枚绿色代币时，玩家可以合法地移除其中任意枚或全部，然后往该堆中添加_任意数量_的豆子。 乍看之下，带有 !\!ω\!\!-代币的Nim游戏似乎可能无限进行下去。但事实并非如此！ 如果有人给了你一个所有堆都只包含豆子的Nim局面，你可以事先说出游戏可能持续多长时间。例如，从 nim堆大小为 !\!\\\{1, 3, 4, 8\\\}\!\! 的游戏开始，它不可能超过16回合，因为每回合至少从一堆中取走一颗豆子，而当有人取走最后一颗豆子时游戏结束。 如果游戏从大小为 !\!\\\{1, 3, 4, 8, \\omega\\\}\!\! 的nim堆开始，你无法知道它会持续多久。如果你猜测它将在 !\!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，然后游戏结束。 序数的这一性质被称为**良基性**。我们说序数是**良基的**。 注意，这是序数的特殊性质，并非所有类型的数都有。例如，正有理数就没有这一性质。从 !\!1\!\! 开始，你可以降到更小的 !\!\\frac12\!\!，然后到更小的 !\!\\frac13\!\!，如此循环，一直向下，越来越小，但永远达不到零。如果Nim游戏中的豆子能分成无限小的碎屑，那么游戏可能永远不会结束。但带有序数的Nim游戏总会结束，因为序数是良基的。你可以一路向上，升到越来越疯狂的无限序数，但无论升得多高，你都无法一路向下永远持续下去——经过_有限_时间后，你必然会降到零。 良基序是递归程序的理论支柱。当我们编写递归函数时，我们希望确保它能终止。这意味着，如果一个函数用不同的参数调用自身，那么新参数必须比原来的_小_。“更小”可能指数值更小，但也可能指其他多种情况。如果函数正在处理目录树，“更小”可能指“深度更浅”。如果函数正在对列表排序，“更小”可能指“乱序元素更少”。递归的本质在于缩减不能无限持续下去。函数最终会达到数字零，或者只包含文件的目录，或者没有未排序元素的列表，然后任务就完成了。 在下一篇文章中，我们将看到一种理解无限nim堆的方法，它比用各种形状和颜色的代币拼凑起来的方式更统一。 *[其他文章归类于 /math/ordinals (https://blog.plover.com/math/ordinals)] 永久链接 (https://blog.plover.com/math/ordinals/02-wellfoundedness.html)*