Yesterday I mentioned the Ken Thompson ACM Lecture in my blog. Now that I am Vicodin-free and thinking clearly, I understood why the concept tickled me so. (Well, it would've tickled me regardless, since the computer-engineering concept in it can only be described as cute; it just somehow connects to something else in my brain that made it even more enjoyable.)
What I speak of is the concept of Bootstrapping (named after the phrase "pick oneself up by his own bootstraps"). The basic idea behind bootstrapping is something dangerously close to circular reasoning. It goes something like this:
The key to the procedure, then, is of course, the third step. This is where the similarity to Thompson's code injection scheme for C compilers arise. The key insight is that we assume something is small in order to prove that it is actually smaller than what we assumed it being. In a sense, this is even better than self-replicating code: imagine writing a computer program that can write a shorter computer program that does exactly that.... In computer land everything is discrete, so it is impossible for this to continue ad infinitum (if your original computer program takes N bytes, the largest the 1st descendent can be is N-1 bytes, and so on, until the largest the Nth descendent can be is 0 bytes--it cannot even exist!); but in continuum mathematics where we can arbitrarily divide numbers into smaller and smaller chunks, something like this can be possible.