In this issue of “Intractable Problems” I want to discuss various paradoxes that can occur during our work. Now, the Oxford dictionary says that a paradox is a self-contradictory or essentially absurd statement. This term can probably be applied to many aspects of computing, not the least of which is the notion that if a computer cable has one end, then it has another. Somehow this rarely seems to be true, particularly if you are tasked with finding the right end!
Anyway, some paradoxes are real. They illustrate that there are unprovable statements which can be shown to be false if they are false, but they cannot be shown to be true.
Consider the Epimenides paradox, which states: “This statement is false.” Actually, Epimenides, who was a Cretan, really said that “All Cretans are liars!” However, because ethnic and cultural bias is frowned upon today we try to use the more general form that does not single out one specific group of people. The Epimenides paradox is an assertion that is true if and only if it is false. Therefore it is neither true nor false.
Oops! What did I just say? If Epimenides was a Cretan and all Cretans were liars, then Epimenides is a liar, so he must have told a lie when he said that all Cretans are liars, which means that all Cretans are not liars, and we know that Epimenides would not lie, so it must be true that all Cretans are liars, which means …
That’s the problem with paradoxes, they are infernally difficult to prove.
Another paradox attributed to Bertrand Russell, a famous mathematician, deals with sets or collections of things. Russell said, “Consider the set of all sets that are not members of themselves. Is this set a member of itself?” This paradox showed that informal reasoning in mathematics can yield contradictions, and it lead to the creation of formal mathematical systems. Later, in 1931, Gödel demonstrated that virtually all formal systems are incomplete, in each of them there is at least one statement that is true but cannot be proved.
The Russell paradox caused no end of trouble for the mathematicians! Can you imagine yourself working as a mathematician trying to prove a theorem that you know to be true, but which can never be proved! It’s enough to drive a person mad. More importantly, the Russell paradox showed that all of mathematics cannot be built on the unshakable foundation of logic, there is a crack in the foundation. One day all of mathematics could come tumbling down around us.
Our last paradox, known as the Berry paradox, reads: “The smallest positive integer which to be specified requires more characters than there are in this sentence.” The sentence has 114 characters, (counting spaces between the words and the period, but not the quotation marks), yet it supposedly specifies an integer that, by definition, requires more than 114 characters to be specified.
The Berry paradox is rather subtle. To see the paradox, understand that the sentence defines a number which is beyond its capacity to describe. You actually have to step outside of the limits of the problem to be able to solve the problem. This is why it is self-contradictory and absurd.
Still confused? You are asked to find the smallest number that’s bigger than the sentence, but the sentence itself describes this number! And the sentence can’t be the smallest because we are seeking numbers outside the bounds of the sentence !
Still confused? Go back and re-read.
So, what do paradoxes have to do with computers? Well, the Berry paradox was used by computer scientist Gregory Chaitin to prove that every computer, every formal system, and every human production is limited; there are always sequences too complex to be generated, outcomes too complex to be predicted, and events too dense to be compressed.
Does this mean that we can’t build the perfect system? Well, I suppose so. Given that the perfect system doesn’t exist, bankers and accountants should understand that there may be perfectly valid reasons why the numbers won’t always add up. Money can go missing, and it may not always be a mistake. See? The devil made me do it! However, in our next issue I want to show you how we can never build the perfect travel plans for our salespeople. And, I’ll bet that this is an intractable problem, in more ways than one!
1. Chaitin, G. “Randomness and mathematical proof”, Scientific American 232, May 1975, pp. 47-52
2. Chaiten, G. Lecture, “A Century of Controversy over the Foundations of Mathematics” http://www.cs.auckland.ac.nz/CDMTCS/chaitin/lowell.html