This is an excerpt from Bits to Bitcoin by Mark Stuart Day. Bits to Bitcoin is an accessible guide to our digital infrastructure, explaining the basics of operating systems, networks, security, and other topics for the general reader.
To work our way up to this sort of self-mirroring and the problems that arise, let’s consider an even earlier logic problem called Russell’s Paradox. Russell’s Paradox arises from the work of Bertrand Russell, yet another famous logician and philosopher who was a contemporary of Hilbert, Gödel, Church, and Turing.
One way of talking about Russell’s Paradox is to talk about clean-shaven men in a small town with a single male clean-shaven barber. The barber shaves everyone in town who does not shave himself.
The paradox itself arises from trying to classify the barber within the stated rules:
- If he shaves himself, he is not shaved by the barber… which means he doesn’t shave himself. Or…
- If he is shaved by the barber, he is shaved by himself, which means he isn’t shaved by the barber.
With either decision, we arrive at a contradiction. How annoying!
We can acknowledge that this is a paradox, but it seems a bit pointless and pedantic.We might well wonder about its significance to the problem of computability that we are trying to approach. Part of the answer is that the elements in play here will also matter for computability. In particular, to have this paradox we need to have three elements together:
- Universality (a rule that applies to all the clean-shaven men);
- Negation (those who shave themselves are not shaved by the barber);
- Self-reference (men who shave themselves).
If we eliminate any one of these elements, the paradox disappears:
- If we eliminate universality, the barber can simply be an exception to the rule.
- If we eliminate negation, the barber can be both shaved by himself and shaved by the barber.
- Finally, if we eliminate self-reference then we would simply be discussing the set of men who are or aren’t shaved by the barber, which can certainly include the barber.
Halting vs. diverging
Russell’s Paradox is a fine logic puzzle, but why does it have any relevance to computability? We are going to take those same ideas of universality, negation, and self-reference and apply them to the “answerability” of computational questions.
We start with the idea that each process either gives an answer… or it doesn’t. If a process gives an answer, we say that it halts – it doesn’t take any more steps after it comes up with the answer. If a process never gives an answer, we say it diverges – that is, it just fiddles around taking meaningless steps endlessly.
Then we create a process about processes, with a special kind of “clairvoyant” quality. This clairvoyant process can be given a program specifying another process as its input, and will determine (somehow) whether that corresponding process halts or diverges.
Let’s pause here and consider what we’ve done. It doesn’t feel like we’ve done anything wrong… yet. We’ve just said that we are going to build a program that looks at other programs. Examining a program to determine whether it halts or not seems like something useful that a program can do, much the same way that cutting hair is just something useful that a person can do. Indeed, there are real-world examples of programs that examine other programs to determine if the examined programs contain errors. We can view this clairvoyant program as a very simple abstract example of the larger class of programs that examine programs.
Determining whether a program halts is less familiar than cutting hair, but otherwise nothing here seems alarming. Just as it might take a lot of training to cut hair well, it might take a lot of sophistication to build this clairvoyant program. But in the best traditions of mathematics, we’ll just assume we can solve the problem rather than worrying about how!
Building a paradox
For the next step in our pursuit of paradox, we build a negated version of that clairvoyant process. The negated clairvoyant process halts if the input process diverges, and diverges if the input process halts. In contrast to the unknown complexity of building a clairvoyant process, the negation step seems easy and obviously implementable. Whatever you were going to do, just do the opposite.
The final step in assembling this paradox is to ask what happens when the negated clairvoyant process is given itself as input. After all, the negated clairvoyant process is just a process, and its specifying program can be examined just like any other program to determine whether it halts or diverges.
But the situation is dire when we do apply the negated clairvoyant process to itself. If the negated clairvoyant process halts when given itself, then it diverges; but if it diverges when given itself, it halts. Ugh! There is a contradiction, which we can trace back to our assumption that we could build the clairvoyant process.
Once again we used the combination of universality, negation, and self-reference to achieve a contradictory result.