Complexity_ A Guided Tour - Melanie Mitchell [28]
Hilbert’s Problems and Gödel’s Theorem
The study of the foundations and limitations of computation, which led to the invention of electronic computers, was developed in response to a set of seemingly abstract (and abstruse) math problems. These problems were posed in the year 1900 at the International Congress of Mathematicians in Paris by the German mathematician David Hilbert.
David Hilbert, 1862–1943 (AIP Emilio Segre Visual Archives, Lande Collection)
Hilbert’s lecture at this congress set out a list of mathematical New Year’s resolutions for the new century in the form of twenty-three of the most important unsolved problems in mathematics. Problems 2 and 10 ended up making the biggest splash. Actually, these were not just problems in mathematics; they were problems about mathematics itself and what can be proved by using mathematics. Taken together, these problems can be stated in three parts as follows:
Is mathematics complete? That is, can every mathematical statement be proved or disproved from a given finite set of axioms?
For example, remember Euclid’s axioms from high-school geometry? Remember using these axioms to prove statements such as “the angles in a triangle sum to 180 degrees”? Hilbert’s question was this: Given some fixed set of axioms, is there a proof for every true statement?
Is mathematics consistent? In other words, can only the true statements be proved? The notion of what is meant by “true statement” is technical, but I’ll leave it as intuitive. For example, if we could prove some false statement, such as 1 + 1 = 3, mathematics would be inconsistent and in big trouble.
Is every statement in mathematics decidable? That is, is there a definite procedure that can be applied to every statement that will tell us in finite time whether or not the statement is true or false? The idea here is that you could come up with a mathematical statement such as, “Every even integer greater than 2 can be expressed as the sum of two prime numbers,” hand it to a mathematician (or a computer), who would apply a precise recipe (a “definite procedure”), which would yield the correct answer “true” or “false” in finite time.
Kurt Gödel, 1906–1978 (Photograph courtesy of Princeton University Library)
The last question is known by its German name as the Entscheidungsproblem (“decision problem”), and goes back to the seventeenth-century mathematician Gottfried Leibniz. Leibniz actually built his own calculating machine, and believed that humans could eventually build a machine that could determine the truth or falsity of any mathematical statement.
Up until 1930, these three problems remained unsolved, but Hilbert expressed confidence that the answer would be “yes” in each case, and asserted that “there is no such thing as an unsolvable problem.”
However, his optimism turned out to be short-lived. Very short-lived. At the same meeting in 1930 at which Hilbert made his confident assertion, a twenty-five-year-old mathematician named Kurt Gödel astounded the mathematical world by presenting a proof of the so-called incompleteness theorem. This theorem stated that if the answer to question 2 above is “yes” (i.e., mathematics is consistent), then the answer to question 1 (is mathematics complete?) has to be “no.”
Gödel’s incompleteness theorem looked at arithmetic. He showed that if arithmetic is consistent, then there are true statements in arithmetic that cannot be proved—that is, arithmetic is incomplete. If arithmetic were inconsistent, then there would be false statements that could be proved, and all of mathematics would come crashing down.
Gödel’s proof is complicated. However, intuitively, it can be explained very easily. Gödel gave an example of a mathematical statement that can be translated into English as: “This statement is not provable.”
Think about it for a minute. It’s a strange statement, since it talks about itself—in fact, it asserts that it is not provable. Let’s call this statement “Statement A.” Now, suppose Statement A could indeed be proved. But