Godel, Escher, Bach is one of those books I had heard about forever. I am not sure if I would have had the tenacity to complete it if I hadn’t already had a grounding in Computer Science. Having had courses in Computer Theory made the book go from a treatise on computer science, to a narrative that tied together many ideas into a more cohesive whole.
I have not had reason to revisit the incompleteness theorem since I was first exposed to the Idea in CPT Tubesing’s class back in 1991. At the time I remember thinking “A paradox, big deal.”  GEB is built around the idea that self referential system is inherently incomplete (heh, inheritance…) I wondered what the analogue would be in the world of software systems that I currently inhabit.
To start with: a machine can be converted into a language that can be consumed by another machine. We’ve seen the practical application of that with the current interest in virtual machines. VMware, Xen, Linux KVM , and Microsoft’s HyperV are all technologies that allow you to run multiple virtual x86 based machines on a single physical machine. There is currently a file format, OVF, which allows you to specify everything you need to run a given virtual machine.
So we start with the ability to nest virtual machines. Strangely, that is a problem I had to resolve at work. If you work with the technology that allows you to run virtual machines, called the hypervisor, it helps to be able to virtualize the hypervisor for software development reasons. In my case, it is that I need a “cluster” of hypervisors working together, and I don’t have the physical hardware to do so. With the current technology, we can only nest them two deep: a virtual machine runs inside a virtual hypervisor runs inside a physical hypervisor.
So now we take the machine specified by Godel: A machine that can test another machine. If the inner machine can accept itself, the outer machine rejects it. We then feed the outer machine back into itself. So we have a setup where each machine is defined as a VM, and each is capable of running other VMs inside it. When the VM starts, it gets access to the file system at the top level and just keep remount it inside the inner VMs. From that file system, it goes to a known location and reads in the machine it is supposed to execute to test. When the outermost machine tests itself, it sets the “test this machine” path to it’s own OVF file.
The pseudocode looks like this:
if (execute (ovffile) == true) return false;
Where execute loads up the VM, runs it, including some default program (say an init process) that returns a boolean value. What will happen is that each level of nesting will call another level, and so on ad infinitum. What we have here is a recurrence relation with no base case. This is really no different than something like this:
bool call_myself;
bool call_myself(){ return !call_myself()};
If you were to attempt to run this code (java or C++, or even straight C with a #define for bool) you would get a stack overflow error, and see a call stack where each level is “call_myself.”
Thus the incompleteness of the system comes from an incomplete definition of a recurrence relation. This last bit of code is basically the programmatic equivalent of stating “This sentence is a lie.”