Are Impossibility Proofs Possible?
What is the role of impossibility proofs in science?
Alan Turing is of course famous for his machine based notion of what computable means—what we now call, in his honor, Turing Machines. His model is the foundation on which all modern complexity theory rests; it is hard to imagine what theory would be like without his beautiful model. His proof that the Halting Problem is impossible for his machines is compelling precisely because his model of computation is so clearly “right.” Turing did many other things: his code-breaking work helped win the war; his work on AI is still used today; his ideas on game playing, biology, and the Riemann Hypothesis were ground breaking.
Today I plan to talk about the role of negative results in science, which are results that say “you cannot do that.” I claim that there are very few meaningful negative results; even Turing’s result must be viewed with care.
You may know that Turing took his own life after being treated inhumanely by his own government. Just the other day the British Prime Minister, Gordon Brown, said that the treatment of Alan Turing was “appalling.”—the full statement is here. Part of Brown’s statement is:
Turing was a quite brilliant mathematician, most famous for his work on breaking the German Enigma codes. It is no exaggeration to say that, without his outstanding contribution, the history of World War Two could well have been very different. He truly was one of those individuals we can point to whose unique contribution helped to turn the tide of war. The debt of gratitude he is owed makes it all the more horrifying, therefore, that he was treated so inhumanely. In 1952, he was convicted of “gross indecency” – in effect, tried for being gay. His sentence – and he was faced with the miserable choice of this or prison – was chemical castration by a series of injections of female hormones. He took his own life just two years later
So on behalf of the British government, and all those who live freely thanks to Alan’s work I am very proud to say: we’re sorry, you deserved so much better.
The terrible treatment of one of the greatest mathematicians that ever lived cannot be undone, but we will continue to honor him every time we use his intellectual legacy.
I have a story that I had planned for today about Turing. The story and most of the post was written before Brown’s solemn statement. The story—I believe—shows something interesting about Turing’s character. I hope that the story is still appropriate to present—I think it still is, and I hope that you agree.
There are many stories about Turing—one of my favorites took place right after the start of World War II. At the time, Turing was working at Bletchley Park in England as a code-breaker. This work was fundamental to the war effort and eventually helped to win the war against Germany—especially fighting U-boats in the North Atlantic.
Right after the fall of France in 1940, it seemed that Germany might invade England at any moment. Turing wanted to be ready to fight, but he had no idea how to fire a rifle, so he signed up for the Home Guard. This was a part-time way to join the army and learn the basics of firearms.
When he joined, the form that he had to sign asked the question:
“You understand by signing this form that you could be drafted into the regular army at any moment.”
He signed the form, but he answered the question “No.” An official apparently filed it, without bothering to read it. Turing then went to enough meetings to learn how to fire a rifle. When it became clear that England was not going to be invaded, he stopped going to the meetings.
The Home Guard officer for his locale later decided to call up Turing into the regular army. Little did the officer know that there was no way that this could ever have happened, since the secret work Turing was doing was critical to the war effort, Prime Minister Winston Churchill would have stopped it personally.
Turing went to see the officer anyway. At their meeting, the officer pointed out that Turing had signed a form that allowed Turing to be put directly into the army. Turing smiled and said, “Take a look at my form.” There, where it said, “You understand by signing this form that you could be drafted into the regular army at any moment,” was Turing’s answer “No.” Apparently, Turing was thrown out of the meeting.
Let’s now go on to discuss impossibility results, including the Halting Problem.
Can They Do That?
I love far-side cartoons. One of my favorites, as I have mentioned before, is a cartoon of a western scene circa mid-1800′s: the cowboys are in a wooden fort shooting at the attacking indians. The indians do not have rifles, like the cowboys, but the indians have bows and arrows and are shooting burning arrows at the cowboys. Some have hit the wooden fort, which is starting to burn. One cowboy says to another, “are they allowed to do that?”
In my opinion this is crux of why an impossibility proof (IP) can be misleading. Of course the indians can shoot burning arrows or any kind of arrow they wish, even if the cowboy’s wooden fort is not prepared for them.
Thus, to me the key issue with any IP is whether the rules of what is or is not allowed is complete. The IP is only as strong as the assumptions of what the “attackers” can do. If the assumptions are too weak, then the IP results can be meaningless.
“Impossibilities are merely things of which we have not learned, or which we do not wish to happen.”
I like the latter part of this quote: “which we do not wish to happen.” I think many IP’s have that flavor.
Over the years many IP’s that were later shown to be not so impossible—that is they were wrong. I would like to point out a few of my personal favorites. They all failed because their assumptions were incorrect: they did not allow for “burning arrows”.
Halting Problem: One of the great IP’s is the impossibility of deciding whether or not a program will halt. Of course, this is due to Turing, and seems to be a very strong result. Not only is the halting problem impossible, but by Rice’s Theorem any property of a program that depends on the program’s behavior is impossible to decide in general. This theorem is due to Henry Rice.
Yet, there is a simple observation: most “real” programs are written in such a way that it is often quite easy to see that they halt. If a program uses only for loops, for example, with fixed bounds, then it must halt. For many other classes of programs also it is not hard to see that they will halt.
So is the halting problem really impossible? Yes it is. However, that does not mean that the halting problem is impossible for programs that arise in practice. For example, Byron Cook of Microsoft has worked on a system called the TERMINATOR. This project has had good success in discovering if a program can potentially hang the operating system. See this also for more details.
Is the halting problem impossible: yes in general, but perhaps not in most examples that we care about. Perhaps.
Trisecting Angles: Pierre Wantzel proved in 1837 that the ancient Greek problem of trisecting a general angle with a straight-end and a compass is impossible. The proof shows that the angle that arises for some trisections is an angle that cannot be constructed with these limited tools. It is a rock-solid IP, but as Underwood Dudley points out in his wonderful book, the proof has not stopped many amateurs from trying to find constructions that circumvent the proof.
The problem is solvable with slightly different tools, which are not much more complex than the allowed ruler and compass. If the ruler has two marks on it, then there is a solution. Or given a piece of string, one can trisect any angle. Again Wantzel’s proof is an IP that is correct, but it does not completely close all the doors on the problem. A marked ruler or the piece of string can play the role of the burning arrows.
Airplanes: William Thomson, Lord Kelvin, is famously quoted as saying, “I can state flatly that heavier than air flying machines are impossible.” However, there is some evidence that he did not say this, and even if he did I doubt that he had a real IP. So I will not count this as a flawed IP.
Rockets: There was a paper published in the early 1900′s on the possibility of a chemical rocket ever getting into orbit. The paper gave a careful and tight IP that showed this was impossible. Of course, today, there are countless satellites in orbit around the Earth, so where was the error in the IP? The paper used careful and correct laws of physics and reasonable assumptions about the amount of energy that could be obtained from chemical reactions.
The mistake was simple: the proof assumed implicitly that the rocket had constant mass. Clearly, as a rocket burns fuel it gets lighter, and this was the mistake that killed the IP. Note, there was a real insight in the flawed IP—the motivation for why rockets usually have many stages. Rockets stages allow mass to be shed at a quicker rate than just losing the mass of the fuel that is burnt. Early rockets used three or even four stages to place their payload into orbit, while today it is possible to get into orbit with two stages—one might argue that the shuttle uses stages.
By the way I have lost the paper citation, and would love if someone can find the paper for me.
Along similar lines, when physicist Robert Goddard published his groundbreaking paper “A Method of Reaching Extreme Altitudes”, the New York Times reacted sharply, by heaping severe criticism on his ideas, even attacking his integrity. See here for the relevant portion of the NYT article. The basis of their attacks was the same as above, implicitly assuming that a fixed mass system cannot accelerate in a vacuum. See here and here for more details on this.
After a gap of nearly 50 years, three days before man set his foot on the moon, the NYT eventually came around and rescinded their stance — they published a short correction article to their 1920 article.
Crypto Protocols: Crypto-protocols are one of great sources of IP’s that are often later shown to be flawed. The reason is simple: the IP rests on assumptions about what the attacker can do. In cryptography the attacker is often well motivated, has large resources, and is often very clever. Thus, the IP’s are “broken” not by direct attacks, but by showing that the IP’s assumptions are flawed.
A famous one is Johan Håstad attack on RSA, which used the Chinese Remainder Theorem (CRT) —recall CRT is one of my favorite theorems. He showed that sending the same message via many RSA systems was dangerous: the message could be found without directly breaking RSA. I was involved in another attack that also used the CRT to break crypto-systems such as RSA in the presence of faults. This is joint work with Dan Boneh and Richard DeMillo.
More recent examples are problems with crypto-protocols that are composed with other protocols, and also protocols that encrypt messages that are used later as keys in another system. The latter are called circular security models, and there is active research into their properties.
Quantum Protocols: Charles Bennett and Gilles Brassard in 1984 suggested how to use quantum mechanics to build a key exchange system that would be impossible to break. They had an IP that was not based on a complexity assumption, but on the correctness of quantum mechanics. This was a brilliant idea then, and is still one of the great insights about practical applications of quantum methods to security.
However, the exact proof that the system, BB84, is secure is not quite right. There are a number of attacks that were missed in the proof. For example, some sources of single photons sometimes put out multiple photons. This allows the photon number splitting attack to be applied. Again these were flaws in the assumptions of what an attacker could do.
So what is the role of IP? Are they ever useful? I would say that they are useful, and that they can add to our understanding of a problem. At a minimum they show us where to attack the problem in question.
If you prove that no X can solve some problem Y, then the proper view is that I should look carefully at methods that lie outside X. I should not give up. I would look carefully—perhaps more carefully than is usually done—to see if X really captures all the possible attacks.
What troubles me about IP’s is that they often are not very careful about X. They often rely on testimonial, anecdotal evidence, or personal experience to convince one that X is complete.
The open problem is to please view all IP’s with a certain degree of doubt—question, question, and question the assumptions.
I of course am open to P=NP as a possibility. But even a proof that PNP viewed as an IP should be taken as a direction, not as an absolute statement. I have talked before about the many ways that PNP can be true, please think hard about these.