Minds aren't magic

Paul Crowley

Month: July, 2016

Expressing computable ordinals as programs

I loved John Baez’s three-part system on large countable ordinals (123) but something nagged at me. It felt like a description of an algorithm in prose, and I feel like I don’t really understand an algorithm until I’ve implemented it. But what does it mean to implement an ordinal?

I found a couple of answers to that online. One is the definition of a recursive ordinal, and the other is Kleene’s O. However both seemed pretty unsatisfactory to me; I wanted something that could naturally express operations like addition/multiplication/exponentiation, as well as expressing finite ordinals.

Here’s where I ended up: we express an ordinal as a set of lexicographically-sorted and well-ordered binary strings with the “prefix property” that no string in the set is a prefix of any other. If \mathrm{ord}(A) is the ordinal represented by set A, we have

  • 0 = \mathrm{ord}(\{\})
  • 1 = \mathrm{ord}(\{\epsilon\}) (\epsilon is the empty string)
  • 2 = \mathrm{ord}(\{0, 1\})
  • 3 = \mathrm{ord}(\{0, 10, 11\})
  • 4 = \mathrm{ord}(\{0, 10, 110, 111\})
  • \omega = \mathrm{ord}(\{0, 10, 110, 1110, 11110, \ldots\})
  • \omega + 1 = \mathrm{ord}(\{00, 010, 0110, 01110, 011110, \ldots , 1\})
  • \omega^2 = \mathrm{ord}(\{00, 010, 0110, 01110, \ldots , 100, 1010, 10110, \ldots, 1100, 11010, \ldots, 1110, 111010, \ldots\})

These are just samples: for every ordinal, there are infinitely many sets that could represent it.

Addition and multiplication are easy here:

  • \mathrm{ord}(A) + \mathrm{ord}(B) = \mathrm{ord}(\{0 \cdot a | a \in A\} \cup \{1 \cdot b | b \in B\})
  • \mathrm{ord}(A)\mathrm{ord}(B) = \mathrm{ord}(\{b \cdot a | a \in A,  b \in B\})

Exponentiation is a bit harder, I use this idea: consider a function f: B \rightarrow A with finite support. Let \{b_1, b_2, ... b_n\} = \mathop{\mathrm{supp}}(f) where b_1 > b_2 > ... > b_n. Then we represent this function as 1 \cdot b_1 \cdot f(b_1) \cdot 1 \cdot b_2  \cdot f(b_2) \cdot \ldots \cdot 1 \cdot b_n \cdot f(b_n)  \cdot 0 . If C is the set of all such representations for all such functions f, then \mathrm{ord}(A)^{\mathrm{ord}(B)} = \mathrm{ord}(C)

Instead of limits, I define an infinite sum function. Given a function f: \mathbb{N} \rightarrow \mathcal{P}(\{0,1\}^{*}) we have

  • \sum_{i=0}^\infty \mathrm{ord}(f(i)) = \mathrm{ord}(\{1^i \cdot 0 \cdot x| i \in \mathbb{N}, x \in f(i)\})

The obvious way to represent these sets as programs would be as functions that test for membership of the set. It should be clear how to implement addition and infinite sum with this representation, and multiplication is only a little more complicated. Unfortunately I don’t see how to do exponentiation, because of one small wrinkle: if we’re to get the right answer for finite exponents, we must ensure that every one of our f(b_i) entries are non-zero, ie not the smallest elements of B, and we have no way to find that. So instead I propose a slight wrinkle: we implement instead a function which tells us whether a string is a prefix of any string in the set.

I’ll try to share code implementing all this ASAP, but I wanted to put the ideas out there first. Thanks!


I’m writing this now because I anticipate linking to it over and over again; this fallacy isn’t going anywhere.

Journalists have got very good at using the word “comparing” to turn the most innocuous statement into a gaffe, through a simple trick of equivocation. Most recently, Jeremy Corbyn is accused of “comparing” Israel and ISIS, but a search for “accused of comparing” finds many other examples. The pattern goes like this: a politician says something like “just as one doesn’t put a vampire in charge of a blood bank, one shouldn’t put the press in charge of protecting privacy”. This use of analogy is one sense of the word comparing. However, many now seem persuaded that “comparing” really means “equating”. Thus we start with someone using a vivid analogy to make a point like “you should consider someone’s partisan motivations before giving them an important responsibility” and through the magic of this word, this becomes “Politician claims Rupert Murdoch kills people and drinks their blood”, which as far as I know he doesn’t.

I’m even less of a fan of Dan Quayle than of Jeremy Corbyn, but he too fell foul of something very similar, though the word itself wasn’t used. In the 1988 vice-presidential debates, he used the example of JFK to argue that a short Congressional service need not be a bar to high office. Lloyd Bentsen replied with the now-famous put-down “Senator, I served with Jack Kennedy. I knew Jack Kennedy. Jack Kennedy was a friend of mine. Senator, you’re no Jack Kennedy.” Of course Quayle was claiming no such thing; he was simply showing that the charge against him proved too much. But this deliberate misunderstanding is one of the most celebrated lines in VP debates.

The thing that’s most annoying about this is that it’s natural to reach for the most extreme example to prove your point. If we oppose vigilante justice even for murder, we certainly oppose it for littering. If we should defend the right to free speech even of Nazis, we should certainly defend it when it comes to, say, Tories. If we’re not going to hold all Saudis responsible for Osama bin Laden, we’re certainly not going to hold all Canadians responsible for Justin Bieber. To me this seems like a normal move in argument, but if I were a politician I couldn’t say any of these things, for fear of being accused of “comparing” Bieber to OBL.

Update: this comic makes a similar point very well. Update: Julia Galef discusses the comic. Thanks to Michael Keenan for both links, on FB.