The Universe of Discourse

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

Previously:

1. Ordinal numbers and basic set theory
2. Ordinals as nim-heaps
3. Nim always ends, even with infinite ordinals
4. Infinite Nim as a coin-moving game
5. 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, whether or not !!s\in S!!. 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? This can only happen if !!S!! is finite, so the program will certainly halt on its own, and when it does that user has their answer.)

Not every program is productive

The non-productive program I showed above is silly, but productivity isn't something you can always guarantee, if you want the data in sorted order. Some orders work, and some don't.

The conventional order for strings, implemented by Python's < operator or C's strcmp, is called lexicographic, which means “dictionary-style”. There are some sets of strings for which no productive program can print all the strings in lexicographic order.

For example, consider the set of all strings that are made up of either all as or all bs:

    a
    b
    aa
    bb
    aaa
    bbb
    aaaa
    bbbb
    …

Notice that this list is not in lexicographic order, because in lexicographic order, the string aa should come out before b.

There is no productive program to print this set in lexicographic order. Why not? Because in lexicographic order the list begins like this:

    a
    aa
    aaa
    aaaa
    aaaaa
    …

and the program never gets around to printing any of the strings with bs. This is analogous to how the non-productive example earlier waited to print even numbers until after it was finished with the odd numbers. To print these strings in lexicographic order would meansto print the strings beginning with b after printing the strings beginning with a. But the program never does finish with the strings beginning with a. The program is supposed to produce bbb, but it never does, no matter how the user waits. And it's supposed to reach a point where the user can be sure that banana will not come out, but it never does that either, it keeps printing as and never prints a string like bbb that comes after banana in lexicographic order.

The problems with lexicographic order are even worse than this example shows. Consider this set of strings:

    b
    ab
    aab
    aaab
    aaaab
    aaaaab
    …

Notice again: not lexicographic order, because b should come out last, not first. But what should come first? A program to print these strings in lexicographic order can't even get started, because in lexicographic order, this list of strings doesn't have a first element! The program can't print out b first because all the a strings were supposed to come out before that. And it can't print out ab first because aab was supposed to come out before that. And it can't print out aaaaaaaaab because aaaaaaaaaaaaaaab was supposed to come out before that. Whatever string the program tries to print out first, it will have made a mistake!

If you're trying to print out an ordered, infinite list of strings, lexicographic order just won't do.

Lexicographic order isn't well-founded

In an earlier article in this series we talked about “well-founded” orders. In a well-founded order, every set of items has a first item, if it has any at all. Writing a productive program for a well-founded order is easy:

• Repeat forever:
  Question: Are there any items left to print?
  No: Halt
  Yes:
  • Let !!P!! be the set of unprinted items
  • Let !!s!! be the first item in !!P!!
    (There must be one, because we're printing the items in a well-founded order)
  • Print !!s!!

As we saw, the conventional lexicographic order is not well-founded for strings. Some sets simply don't have a lexicographically first element.

So in circumstances where we might be handling infinite data streams, we often prefer a different string ordering, almost as simple and considerably better-behaved.

Shortlex order

You already know this one, although perhaps not by that name. It's nothing more than the order we use for regular numerals like 723. It's not lexicographic, because as you've probably noticed, in lexicographic order, 10 comes before 2. Here's the track listing of my copy of Quadrophenia, as listed by the Unix ls program:

    1 I am the sea.mp3
    10 I've had enough.mp3
    11 515.mp3
    12 Sea And Sand.mp3
    13 Drowned.mp3
    14 Bell Boy.mp3
    15 Doctor Jimmy.mp3
    16 The Rock.mp3
    17 Love Reign O'er Me.mp3
    2 The real me.mp3
    3 Quadrophenia.mp3
    4 Cut my hair.mp3
    5 The punk and the godfather.mp3
    6 I'm one.mp3
    7 The dirty jobs.mp3
    8 Helpless dancer.mp3
    9 Is it in my head.mp3

Hey, wait, why did ls put track 17 ahead of track 2? Because ls lists files in lexicographic order, and in lexicographic order, 17 comes ahead of 2 for the same reason that agony and the other ag- words come before bony and the other b- words in the dictionary.

If you name your files after numbers, then when the computer lists them in lexicographic order, they won't be in numeric order. Numeric order isn't lexicographic. But numerals, in shortlex order are in numeric order, and of course it's trivial to print all possible numerals in numeric order.

The rule to compare two strings in shortlex order is:

1. If the strings are different lengths, the shorter one comes first.
2. If they're the same length, compare them lexicographically.

Compare the shortness first, and use lexicographic comparison as a tiebreaker. Hence “short” + “lex”.

Consider what this means for numerals. Here's a list of binary numerals from !!0!! to !!15!!:

        0
        1
        10
        100
        1000
        1001
        101
        1010
        1011
        11
        110
        1100
        1101
        111
        1110
        1111

It looks strange because it's in lexicographic order — all the numerals that begin with 10 appear before all those beginning with 11, which means that 1000 comes before 11, even though (checking my notes) !!3 \lt 8!!.

If we want to print all binary numerals in lexicographic order, we're out of luck. The list starts like this:

        0
        1
        10
        100
        1000
        …

and we never get to printing any of the numerals starting with 11, including 11 itself.

In shortlex order, it's what we expect. We get the numeral for every number, and in numeric order:

    0
    1
    10
    11
    100
    101
    110
    111
    1000
    1001
    1010
    1011
    1100
    1101
    1110
    1111
    …

Unlike lexicographic order, the shortlex order is well-founded. Remember that “well-founded” means that every set of strings has a first element. But in lexicographic order, this set of binary numerals has no first element:

    11
    101
    1001
    10001
    100001
    …

In shortlex order there's no problem. There can't be, because shortlex order is numeric order, and if numeric order wasn't well-founded there wouldn't be a productive program to print all the numerals in order, which of course there is.

The infinite lists that we couldn't put into lexicographic order before give us no trouble in shortlex order. In fact, I listed both in shortlex order already:

    a             b
    b             ab
    aa            aab
    bb            aaab
    aaa           aaaab
    bbb           aaaaab
    …             …

For strings, shortlex order is well-founded, which means that every set of strings contains a first element. Here's why: Consider some set !!S!! and some string !!s\in S!!. The string !!s!! has a length !!\ell!!. Consider the set !!E!! of strings that come before !!s!!. The set !!E!! must be finite because every string that comes before !!s!! in shortlex order has length less than or equal to !!\ell!!, and there are only a finite number of such strings.

If !!E!! is empty, then !!s!! itself is the first string in !!S!!. If !!E!! is not empty, then, being finite, it must have a first element. (Just sort !!E!!.) This first element is the first string in !!S!!. Done.

Wait, why are there are only a finite number of strings with length less than or equal to !!\ell!!? Well, there are only a finite number of strings of length !!0!!. (There's only one.) And there are only a finite number of strings of length !!1!!: If the character set contains !!n!! symbols, there are only !!n!! with length !!1!!. Similarly there are only !!n^2!! strings of length !!2!!, and so on. Since there are only a finite number with each length up to !!\ell!!, we just add up this finite list of finite numbers and the sum is finite. And since every string in !!E!! has length no more than !!\ell!!, the number of strings in !!E!! is at most this finite number.

Coming next: Shortlex order is well-founded on sequences of ordinals.

I made Claude sit in a chair in the corner and watch silently while I wrote this.

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