I happened to have a trade-off rant today in my Algorithms Programming Application Software! class (*Now aint that exotic?!*), I got a metaphor involving the undescribable numbers for my teacher. An interesting confusion came up from him in the comments about just what that meant. Instead of answering it with a comment, I decided that it justified a post of its own. It's a fascinating topic which is incredibly counter-intuitive. To me, it's one of the great examples of how utterly wrong our intuitions can be.

Numbers are, obviously, very important. And so, over the ages, we've invented lots of notations that allow us to write those numbers down: the familiar arabic notation, roman numerals, fractions, decimals, continued fractions, algebraic series, etc. I could easily spend months on this blog just writing about different notations that we use to write numbers, and the benefits and weaknesses of each notation.

But the fact is, the vast, overwhelming majority of numbers cannot be written down in any form.

That statement seems bizarre at best. But it does actually make sense. But for it to make sense, we have to start at the very beginning: What does it mean for a number to be describable?

A describable number is a number for which there is some finite representation. An indescribable number is a number for which there is no finite notation. To be clear, things like repeating decimals are not indescribable: a repeating decimal has a finite notation. (It can be represented as a rational number; it can be represented in decimal notation by adding extra symbols to the representation to denote repetition.) Irrational numbers like π, which can be computed by an algorithm, are not indescribable. By indescribable, I mean that they really have no finite representation.

As a computer science guy, I naturally come at this from a computational perspective. One way of defining a describable number is to say that there is some finite computer program which will generate the representation of the number in some form. In other words, a number is describable if you can describe how to generate its representation using a finite description. It doesn't matter what notation the program generates it in, as long as the end result is uniquely identifiable as that one specific number. So you could use programs that generate decimal expansions; you could use programs that generate either fractions or decimal expansions, but in the latter case, you'd need the program to identify the notation that it was generating.

So - if you can write a finite program that will generate a representation of the number, it's describable. It doesn't matter whether that program ever finishes or not - so if it takes it an infinite amount of time to compute the number, that's fine - so long as the program is finite. So π is describable: it's notation in decimal form is infinite, but the program to generate that representation is finite.

An indescribable number is, therefore, a number for which there is no notation, and no algorithm which can uniquely identify that number in a finite amount of space. In theory, any number can be represented by a summation series of rational numbers - the indescribable ones are numbers for which not only is the length of that series of rational numbers infinite, but given the first K numbers in that series, there is no algorithm that can tell you the value of the K+1th rational.

So, take an arbitrary computing device, φ, where φ(x) denotes the result of running φ on program x. The total number of describable numbers can be no larger than the size of the set of programs x that can be run using φ. The number of programs for any effective computing device is countably infinite - so there are, at most, a countably infinite number of describable numbers. But there are uncountably many real numbers - so the set of numbers that can't be generated by any finite program is uncountably large.

Most numbers cannot be described in a finite amount of space. We can't compute with them, we can't describe them, we can't identify them. We know that they're there; we can prove that they're there. All sorts of things that we count on as properties of real numbers wouldn't work if the indescribable numbers weren't there. But they're totally inaccessible.