Ants, Cats, and Cantor’s Diagonal
Introduction
When I was a computer science student, I read the first edition of the book "Parsing Techniques - A Practical Guide" by Dick Grune [1] et al. In the ~30 years since, it may be the book I’ve been reminded of most often.
The primary reason for this is that the book goes off on tangents that are sometimes only vaguely related to the book's topic, or even to the immediate context. If you're interested in a subject, details add texture, making it easier to remember. If you just want to get the information you're looking for, these detours can be annoying. "Get to the point already!"
If you've read any of my other blog posts, you may have noticed I tend to go off on interesting (your mileage may vary) tangents as well. I'm not sure whether I inadvertently adopted the writing style or if the book simply matched my preferences and I like it because of that.
Warning: in this blog post, I'm only going off on tangents.
Telescoping
This blog post was triggered by something that happened to me earlier that reminded me of the following quote from the bottom of page 16:
But no, words cannot be broken down any further. The computer scientist is not worried by this. With his love of telescoping solutions and multi-level techniques, he blithely claims that if words turn out to have structure after all, they are sentences in a different language, of which the letters are the tokens.
One of our cats had started sleeping outside, so I left her a bowl of soft food. When I went to collect the empty bowl in the morning, it was crawling with ants. I squatted down and watched their frantic, seemingly random activity for a while. Then, taking a cue from Jain ascetics, I gently blew them off the bowl so I could clean it with hot water and fill it with fresh food.
As I went back inside, I noticed our cats still hadn't fully mastered the magnetic mosquito curtain in the doorframe. They press their snouts against it, recoil as they are startled when the magnets release, and have to try again.
Watching cats failing to learn a simple mechanism and ants scurrying about made me wonder: if there was a being with an intelligence level far above our own (a far more evolved alien, or perhaps even an omniscient deity), what weirdness would it see in our behavior that we, as a species, are completely oblivious to? I'm not referring to the countless flaws many of us already recognize in ourselves and our societies. I mean true blind spots: things that would be obvious to a more advanced intelligence but are inconceivable to us.
I wonder if those beings look down on us with the same amusement at our total lack of sophistication as we do on ants and cats.
No one would have believed
in the last years of the 19th century
that human affairs were being watched
from the timeless worlds of space.
No one could have dreamed we were being scrutinized
as someone with a microscope studies creatures
that swarm and multiply in a drop of water.
- Richard Burton reciting H.G. Wells in Jeff Wayne’s Musical War of the Worlds.
Knowability
This is the very first sentence of the preface of the Parsing Techniques book:
Parsing (syntactic analysis) is one of the best understood branches of computer science.
Obviously, I already knew that we know more about some subjects than others, but the way this was phrased ("one of the best understood branches") indicates that you might be able to order or at least categorize bodies of knowledge by how well humanity understands them. This suggests we don’t just know things about a subject; we also have a good sense of how large our blind spot must be. This fascinated me because I've never been particularly good at mathematics, and I truly have no idea how much I don't know about it, or how I'd approach the task of estimating how much I don't know about it.
To get my fascination across, I'd like you to take a look at this image of the "Mathematics Trench." If you're anything like me, you might recognize a few items near the top, and feel surprised and humbled by how much lies beyond your horizon of mathematical knowledge.
Then consider: the depth of this trench may merely be the horizon of today's greatest human math geniuses. But the things we (to quote from the image) "require Advanced AI" for, may be the homework assignment of a first grader of an alien civilization...
As a side note, the name "Hairy Ball Theorem" made me chuckle.
Cantor's Diagonalverfahren
We can lie in the grass on a clear night, look at the stars, and know that the universe may go on indefinitely in every direction, but at the same time this is still impossible to comprehend.
Section 2.1.3.4 in the Parsing Techniques book discusses the diagonalization process, or, in German, Diagonalverfahren (verfahren = process, or procedure), by Georg Cantor. I was immediately intrigued and spent the next few days reading about infinity, the fact that infinities exists in different sizes, countability, and related concepts.
This section contains some mathematics. If that isn't your thing, feel free to skip to the paragraph after the zipper image -- you won't miss the main point.
Take the set of natural numbers, ℕ: { 0,1,2,3,... } and the set of real numbers, ℝ, which contains basically any number you can think of (except complex numbers). You can count the natural numbers; you'd never finish, but given enough time every natural number would eventually appear in the sequence.
Now imagine the set of all real numbers between 0 and 1. Since that set is bounded at both ends, you might expect it to be smaller than (unbounded) ℕ. It is not! Let's say someone said they put all those numbers (that is, the real numbers between 0 and 1) in a complete list; something like this:
1: 0.123456...
2: 0.420690...
3: 0.314159...
4: 0.390005...
etc. Of course, normally you'd go about this more methodically! [2]
Georg Cantor's Diagonalverfahren is the process of creating a number that is guaranteed to not be on that list -- even though, as I wrote, the list is supposed to be complete. It goes like this:
- Take the first decimal of the first number and add 1; wrap 9 to 0
- Take the second decimal of the second number and add 1
- Take the nth decimal of the nth number and add 1
(Note that we went over the list in a diagonal, hence: Diagonalverfahren!)
Continue forever. The resulting number differs from the first listed number in the first digit, from the second listed number in the second digit, and so on. Therefore, it cannot be equal to any number on the list. No matter how you try to list the real numbers, you'll always miss some. This is what it means for the real numbers to be uncountably infinite.
The countability of a set means that the members of that set can be made to correspond to the members of ℕ. For example, the set of whole numbers, ℤ: { ...,-2,-1,0,1,2,... } can be transformed uniquely into the numbers from ℕ. This often surprises people, because ℤ seems to contain "twice as many" numbers. Yet it's easy to explain: for each value x of ℤ,
- if x < 0, multiply it by -2 and subtract 1.
- if x > 0, multiply it by 2
If you imagine it, it's as if you're merging both sides (viewed from 0) of the number line like the teeth of an (infinitely long) zipper.On the left zipper tape, negative values of ℤ are transformed to the odd values of ℕ; on the right zipper tape, positive values of ℤ are transformed to the even values of ℕ. Zero stays in place. After the merge, the result is simply ℕ again. Infinity is so cool!
Most of what I know about infinity comes from the time I spent studying the subject 30 years ago, started by the Parsing Techniques book. I sometimes use that knowledge as a tool to make sense of things I would otherwise not understand; probably sometimes in a way or context that a proper mathematician would frown upon (see: Law of the Instrument), but I don't remember ever having to backtrack.
On this blog I used a few simple references to eternity/infinity. See: "Even that amount of time is still only a negligible fraction of eternity", and "I think I'm crazy".
Conclusion
I'm intrigued by how much we don’t know, and yet how confidently we move within the boundaries of what we can know. Like ants around a bowl, or cats at a curtain, we navigate a world that likely contains structures we cannot even perceive. Somewhere, possibly forever out of our reach, there may be ideas many orders of magnitude more transformative to humanity than Cantor’s ideas were to me.
Quietly existing, waiting to be noticed by a mind able to see them.
[1] Dick Grune also named Gnome Sort and developed the Concurrent Versioning System (CVS).
[2] You might start like this:
1: 0.10000000...
2: 0.11000000...
3: 0.11100000...
When you extrapolate from this, you may realize that, this way, you'll never get to 0.20000000... This might give you another feel for the sizes of different infinities!