Complexity_ A Guided Tour - Melanie Mitchell [33]
Therefore, our supposition that H’ does not halt on H’ was wrong, so H’ must halt on input H’. But now we have the opposite problem. H’ only halts on its input M if M does not halt on M. So H’ only halts on H’ if H’ does not halt on H’. Another contradiction!
These contradictions show that H’ can neither halt on input H’ nor go into an infinite loop on input H’. An actual machine has to do one or the other, so H’ can’t exist. Since everything that H’ does is allowed for a Turing machine, except possibly running H, we have shown that H itself cannot exist.
Thus—and this is Turing’s big result—there can be no definite procedure for solving the Halting problem. The Halting problem is an example that proves that the answer to the Entscheidungsproblem is “no”; not every mathematical statement has a definite procedure that can decide its truth or falsity. With this, Turing put the final nail in the coffin for Hilbert’s questions.
Turing’s proof of the uncomputability of the Halting problem, sketched above, uses precisely the same core idea as Gödel’s incompleteness proof. Gödel figured out a way to encode mathematical statements so that they could talk about themselves. Turing figured out a way to encode mathematical statements as Turing machines and thus run on one another.
At this point, I should summarize Turing’s momentous accomplishments. First, he rigorously defined the notion of “definite procedure.” Second, his definition, in the form of Turing machines, laid the groundwork for the invention of electronic programmable computers. Third, he showed what few people ever expected: there are limits to what can be computed.
The Paths of Gödel and Turing
The nineteenth century was a time of belief in infinite possibility in mathematics and science. Hilbert and others believed they were on the verge of realizing Leibniz’s dream: discovering an automatic way to prove or disprove any statement, thus showing that there is nothing mathematics could not conquer. Similarly, as we saw in chapter 2, Laplace and others believed that, using Newton’s laws, scientists could in principle predict everything in the universe.
In contrast, the discoveries in mathematics and physics of the early to middle twentieth century showed that such infinite possibility did not in fact exist. Just as quantum mechanics and chaos together quashed the hope of perfect prediction, Gödel’s and Turing’s results quashed the hope of the unlimited power of mathematics and computing. However, as a direct consequence of his negative answer to the Entscheidungsproblem, Turing set the stage for the next great discovery, electronic programmable computers, which have since changed almost everything about the way science is done and the way our lives are lived.
After publishing their complementary proofs in the 1930s, Turing and Gödel took rather different paths, though, like everyone else at that time, their lives were deeply affected by the rise of Hitler and the Third Reich. Gödel, in spite of suffering from on-and-off mental health problems, continued his work on the foundations of mathematics in Vienna until 1940, when he moved to the United States to avoid serving in the German army. (According to his biographer Hao Wang, while preparing for American citizenship Gödel found a logical inconsistency in the U.S. Constitution, and his friend Albert Einstein had to talk him out of discussing it at length during his official citizenship interview.)
Gödel, like Einstein, was made a member of the prestigious Institute for Advanced Study in Princeton and continued to make important contributions to mathematical logic. However, in the 1960s and 1970s, his mental health deteriorated further. Toward the end of his life he became seriously paranoid and was convinced that he was being poisoned. As a result, he refused to eat and eventually starved to death.