Most people that work with me are surprised to learn that I test at the far end of the introversion scale on the
Myers-Briggs Type Indicator personality test (I'm an INTJ). Since I have a reputation as a very hands-on engineer, they might also be surprised by the fact that I enjoyed taking a lot of computer science theory classes when I was in graduate school: formal languages, computability, algorithms, etc. I insist on finding practical applications for this stuff all the time. And occasionally I entertain myself by thinking about things like
Gödel Numbers.
In 1931, philosopher, logician, and mathematician
Kurt Gödel showed how you could take any formal language and represent it as a mathematical function by encoding the symbols of the language numerically and representing the productions of the language as a function that operates on the resulting numbers. Whenever you have formal systems A and B, showing that one can be converted into the other is always a win, because it's a form of code reuse: proving something about A now also applies to B. It didn't take long to show that a Gödel number could be represented as a string that could be operated on by a
Turing Machine, adding yet another formal system to the party.
You can trivially apply this to any piece of software as well. Just take a core dump of your program's initial state in memory. You can think of this result as a hexadecimal representation of its Gödel number. Now take another dump of your program after every instruction executes. You end up with a series of Gödel numbers. Now write a single mathematical formula that generates this series of numbers. You have just converted your program into a abstract function amenable to all sorts of formal analysis. True, it's so large and ugly that such analysis may be intractable, but it's at least theoretically possible.
Remember those intelligence tests you took in grade school where you had to choose the next number in a sequence? I am sorry to inform you that any number can be the correct answer. It is trivially easy to write a mathematical function to generate any arbitrary sequence of numbers. As Mrs. Overclock (a.k.a Dr. Overclock, Medicine Woman) frequently points out, the fact that she and I both did well in school has more to do with the fact that we are good at taking standardized tests, not that we're necessarily smart. Of course, knowing what answer is expected is itself a useful life skill. But I digress...
Theoretical computer scientists are fond of talking about Turing Machines with infinitely long tapes. They do this mostly so that the are not constrained by physical limitations. What they really mean is "the tape is just as long as it needs to be". The fact that there are algorithms that ultimately try to march along to the end of an infinite tape is part of the fun. This is a form of the
Halting Problem.
We can do this with our abstract mathematical function too. We just assume we always have enough bits to represent any possible Gödel number we want to compute. An infinite number of bits should be about right. But what kind of infinity?
It turns out that there are different orders of infinity. Around 1874, set theorist
Georg Cantor showed that indeed while the number of integer numbers (or the cardinality of the set of integer numbers to be more precise) was infinite, and the numbers of real numbers (ditto) was infinite, there had to be more real numbers than integer numbers. That's because we could form a one-to-one correspondence between the set of integer numbers
(... -1, 0, 1, 2, 3, ...)
and the set of real-numbers
(... -1.0, 0.0, 1.0, 2.0, 3.0, ...)
but in between each of those real numbers was another infinite series of entries in the set of real numbers
(... -1.0, ... 0.0, 0.001, ... 0.01, ... 0.1, ... 0.2, ... 1.0, ... 2.0, ... 3.0, ...) .
Cantor called the transfinite number that was the cardinality of the set of all integers
ℵ0 ("aleph null") and the transfinite (but larger) number that was the cardinality of the set of all real numbers
ℵ1 ("aleph one").
What is the relationship between
ℵ0 and
ℵ1? You might expect that since there is an infinite number of entries in the set of real numbers in between each entry that corresponds to an entry in the infinite set of integer numbers, that
ℵ1 would equal
ℵ02, or maybe
ℵ0ℵ0. Not so fast...
Since we can make a one-to-one correspondence, or enumerate, each bit in our hexadecimal Gödel number with an integer number, the number of bits in our infinitely large Gödel number is
ℵ0. So how many unique Gödel numbers can we form from
ℵ0 bits? That's easy for any software developer:
2ℵ0.
Here's where it gets interesting (no, really). What order of infinity is
2ℵ0? It turns out, according to Cantor's
continuum hypothesis, that this value is
ℵ1, the cardinality of the set of all real numbers.
Coincidence? You decide.