The Universe of Discourse

Sun, 19 Jul 2026

The road to epsilon-zero: Nim always ends, even with infinite ordinals

Previously:

Yesterday I talked about the game of Nim, which involves two players taking beans from several piles, and an extension that includes green tokens that behave a bit like infinite piles:

When there's a pile with one or more green tokens, it's legal for a player to remove any or all of them, and then to add any number of beans to the pile.

At first it might seem that Nim with !!ω!!-tokens could go on forever. Not so!

If someone gives you a Nim position where all the piles contain beans, you can say ahead of time how long the game might last. A game starting with nim-heaps of size !!\{1, 3, 4, 8\}!! simply can't last more than 16 turns, because each turn removes at least one bean from a pile, and the game ends when someone takes the last bean.

If the game starts with nim-heaps of size !!\{1, 3, 4, 8, \omega\}!!, you can't know how long it might last. If you guess it will be over in !!1,\!000!! turns, the first player might prove you wrong by replacing the !!\omega!!-token with a pile of !!10,\!000!! beans, and then the game might last up to !!10,\!016!! more turns.

If you guessed at the start that the game would last no more than !!10,\!016!! turns, one of the players might replace the token with a pile of !!1,\!000,\!000,\!000,\!000,\!000,\!000!! beans, or even more. Before the first move, there is no bound that can be placed on how long the game will take to finish.

But what you can say about !!\{1, 3, 4, 8, \omega\}!! is that after at most !!17!! moves, someone will have removed the !!ω!!-token and replaced it with some finite number of beans. And that that point you'll be able to say when the game will end.

!!ω·2!!

Similarly, suppose there is are piles !!\{1, 3, 4, 8, \omega·2\}!!. Remember that !!\omega·2!! is simply a stack of two green tokens. What's the longest this game could last?

As before, we can't say. But we can say that after at most !!17!! turns, at least one of the !!ω!! tokens will have been removed, and there will be at most one !!ω!! token and a possibly very large number of beans, say !!b_1!!. And then after at most !!b_1+1!! more moves, the last !!ω!! token will have been taken if it wasn't before, and only beans will be left, possibly a very large number of beans, say !!b_2!!.

And at that point we will be certain that the game can't last more than !!b_2!! more moves.

So with !!\{1, 3, 4, 8, \omega·2\}!! we can't say how long the game will take to finish.

And we can't say when we will be able to say how long the game will take to finish.

But we can say that in at most !!17!! moves, we will be able to say, not how long the game will take to finish, but how long it will be before we can say how long the game will take to finish.

Estimating programming tasks

This reminds me of a story I once heard from another programmer. He told me his boss had come to him to ask him if he could fix a certain bug. He had replied that he could, and the boss had asked him how long he thought it would take.

He said “I don't know, I have to think about it.”

His boss, being a reasonable woman, asked him when he would be able to tell her.

Again he said “I don't know, I have to think about it.”

The boss, having dealt with this guy before, did not lose her temper. Instead, she asked how long it would take him to figure that out.

“Not more than two days,” he said at once.

“Okay,” she said. “Just to make sure there is no miscommunication, are you telling me that in two days you may not be able to estimate the task, but you will be able to tell me when the estimate will be ready?”

“That's right.”

And they parted amicably, both parties satsified, at least for the time. Communication between management and engineering doesn't always turn out so well!

My friend was apaprently playing the game !!ω·2+1!!. There was only one bean, so one of the !!ω!! tokens would have to have gone by the second day. At that point there would remain !!ω + n!! for some finite number !!n!!, and although my friend wouldn't be able to say at that point how long the game would last, he would know that he would be able to deliver the estimate after at most !!n+1!! more days.

The game must end!

With !!ω·2+1!! we don't know when the game will end, or how long it will be before we know when the game will end.

But we do know that in at most two moves we will know how long it will be before we know how long it will be before the game ends, and that means that we do know that that game will end even though we're quite far away from saying when that will happen.

The argument is always the same: there are only a finite number of beans, and even if both players try to avoid the tokens, the beans will eventually run out and someone will be forced to replace a green token with more beans. Then those beans will run out and someone will be forced to take another token, and so on, until all the tokens are gone, and then when the beans run out the game is over.

Of course, both tokens and beans might go faster than that. But go they will, however slowly and even if only one at a time.

And this is true no matter how many green !!ω!! tokens there are to begin with.

And the same holds true if there are any square !!ω^2!! tokens. Even if the players avoid the square tokens, at some point all the beans and green !!ω!! tokens will be used up and someone will have to replace at least one square !!ω^2!! token with more beans and green tokens, and then those will be used up… and eventually the last square !!ω^2!! token will be gone, and then we're back to the !!ω·n+m!! case of the previous paragraph and the game must end.

But at that point we have defeated English descriptions. We have piled up an infinite sequence of “how long before we can say”s into “We can't say how long before we can say … how long before the game ends”.

Bizarre! And yet we know that even these games must end, although English isn't powerful enough to say how long it will take, or even how long before we will be able to say how long it will take.

Ordinals are well-founded

An ordinal is a set of smaller ordinals. Every move in Nim makes an ordinal smaller. If you keep making numbers smaller you eventually reach 0, and then the game is over.

This property of ordinals is called well-foundedness. We say that ordinals are well-founded.

Note that this that this is a special property of ordinals, not shared by all types of numbers. For example, the positive rational numbers do not have this property. From !!1!! you can go down to the smaller !!\frac12!!, then to the smaller !!\frac13!!, and so on, downward, always downward to smaller and smaller numbers, but never reaching zero. A game of Nim where the beans can be divided into infinitely small crumbs might never end. But a game of Nim with ordinals always ends, because the ordinals are well-founded. You can go up and up forever to crazier and crazier infinite ordinals, but no matter how far up you go, you can't go down and down forever, you must bottom out at zero after a finite time.

Well-founded orderings are the the theoretical backbone of recursive programs. When we write a recursive function, we want to be certain that it will terminate. And that means that if a function calls itself with a different argument, the new argument must smaller than it was. Maybe “smaller” mans numerically less. But it could mean many other things. If the function is processing a directory tree, “smaller” could mean “fewer levels deep”. If the function is sorting a list, “smaller” could mean “fewer items are out of order”. The essence of recursion is that the shrinking cannot continue forever. The function will eventually reach the number zero, or the directory that contains only files, or the list with no unsorted elements, and then it will be done.

In the next article we will see a way to understand infinite nim-heaps in a more uniform way than as a hodgepodge of variously shaped and colored tokens.

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