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

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

The Universe of Discourse

Mark Dominus (陶敏修)

mjd@pobox.com

About me

RSS Atom

12 recent entries

The road to epsilon-zero: Nim always ends, even with infinite ordinals The road to epsilon-zero: ordinals as nim-heaps Starting to understand epsilon-zero It's our language now! I owe my life to a 1913 road rage incident Deciphering basmala My 1992 view of the problems of computer programming in 1992 Egyptian fraction multiplication Update: Here I am at the Sagrada Família Egyptian fractions for 2/105 Did Ahmes find the best expansions for 2/n? Programmers will document for Claude, but not for each other

Archive:

2026: JFMAMJ 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

Subtopics:

Mathematics251 Programming102 Language97 Miscellaneous75 Book50 Tech49 Etymology36 Haskell33 Oops30 Unix27 Cosmic Call25 Math SE25 Law23 Physics21 Perl17 Biology16 Brain15 Calendar15 Food15

-->

Technorati Profile -->

Comments disabled

Sun, 19 Jul 2026

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

Previously:

Ordinal numbers and basic set theory

Ordinals as nim-heaps

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...

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

Related Articles

(no title)

Scientists reverse brain aging, with a nasal spray

AI has torched the market for junior programmers

Al Vigier: Canada's AI strategy shouldn't include secret Palantir bills

The Anatomy of an AI-Native Org