The road to epsilon-zero: Productive programs and well-founded orders

The Universe of Discourse : The road to epsilon-zero: Productive programs and well-founded orders

The Universe of Discourse

Mark Dominus (陶敏修)

mjd@pobox.com

About me

RSS Atom

12 recent entries

The road to epsilon-zero: Productive programs and well-founded orders There are two kinds of theorems The road to epsilon-zero: Coin-moving games with no coins Seven books I keep close because I love them The road to epsilon-zero: Infinite Nim as a coin-moving game “Steph Curry: fluke or breakthrough” ten years later 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

Archive:

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

Mathematics252 Programming102 Language98 Miscellaneous75 Book51 Tech49 Etymology36 Haskell33 Oops30 Unix27 Cosmic Call25 Math SE25 Law23 Physics21 Perl17 Biology16 Brain15 Calendar15 Food15

-->

Technorati Profile -->

Comments disabled

Thu, 13 Aug 2026

The road to epsilon-zero: Productive programs and well-founded orders

Previously:

Ordinal numbers and basic set theory

Ordinals as nim-heaps

Nim always ends, even with infinite ordinals

Infinite Nim as a coin-moving game

Coin-moving games without the coins

Previously we saw how to interpret the difficult-seeming ordinal !!ω^ω!! as a particular ordering of the set of finite sequences of numbers, revealing what seemed like a scary monster as gentle and straightforward.

Now we're going to take a sidetrack into one of my favorite topics, computation with infinite lists. I wrote about this for The Perl Journal in 1997 and then it turned into chapter 6 of Higher-Order Perl and here we are again. Gosh! it just keeps coming back. Like John the Baptist.

Infinite lists

Suppose you have an infinite set of strings — we'll call this set !!S!! for the rest of the article — and you want a program to print them all out. Of course the program can't exactly print them all out, because it will only run for a finite amount of time. But there are more and less useful ways for the program to try.

For each string that the program is supposed to print, we should at least be able to guarantee that the the program will print it, eventually, if we just wait long enough. If this is true then we'll say that the program is “productive”.

Here's a productive program to print the base-10 numerals for all the positive integers:

# Python

i = 1 while True: print(i) i += 1

What would a non-productive program look like? Here's an example of a non-productive program to print the base-10 numerals for all the positive integers:

# Python, silly

i = 1 while True: # print all the odd numbers print(i) i += 2

i = 2 while True: # then print all the even numbers print(i) i += 2

This one tries to print all the odd numbers first, and then all the even numbers. Obviously that doesn't work because it never finishes with the odd numbers. If you were to sit around waiting for the number !!14!!, you'd wait forever. Whereas with the first program, whatever number you are waiting for, even if it is very very big, it will come out eventually.

That's what I meant when I said there are more and less useful ways for a program to try to print an infinite set. The first one never finishes, true, but the way in which it never finishes is much more useful than the way in which the second one never finishes.

Okay, that was a silly example. But there are less silly examples.

Printing strings in sorted order

A productive program is always semidecidable: if a user wants to know if some particular string !!s!! is in !!S!!, and they wait long enough, !!s!! will come out and they have the answer. But if !!s!! isn't in !!S!!, they never find that out! They just wait and wait, wondering if it will come out, and never getting a definitive answer.

If we can get a productive program to produce its strings in sorted order, we can make a better guarantee. The program will be decidable: the user will eventually get an answer, one way or the other. If !!s\in S!! the productive program will eventually produce !!s!!, and the user can stop watching. But if !!s\notin S!!, the program must eventually produce a string that comes after !!s!! in sorted order, and they can quit then. And the program must eventually produce some string that comes after !!s!!, because, being productive, it eventually produces every string in !!S!!.

(What if there is no string in !!S!! that comes after !!s!! in sorted order? Then the productive...

The road to epsilon-zero: Productive programs and well-founded orders

Related Articles

(no title)

Scientists reverse brain aging, with a nasal spray

NHS apologises and admits Palantir have access to identifiable patient data

AI has torched the market for junior programmers

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