In my Dembski rant, I used a metaphor involving the undescribable numbers. An interesting confusion came up 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