Complexity_ A Guided Tour - Melanie Mitchell [29]
It’s not easy to imagine how this statement gets translated into mathematics, but Gödel did it—therein lies the complexity and brilliance of Gödel’s proof, which I won’t cover here.
This was a big blow for the large number of mathematicians and philosophers who strongly believed that Hilbert’s questions would be answered affirmatively. As the mathematician and writer Andrew Hodges notes: “This was an amazing new turn in the enquiry, for Hilbert had thought of his programme as one of tidying up loose ends. It was upsetting for those who wanted to find in mathematics something that was perfect and unassailable….”
Turing Machines and Uncomputability
While Gödel dispatched the first and second of Hilbert’s questions, the British mathematician Alan Turing killed off the third.
In 1935 Alan Turing was a twenty-three-year-old graduate student at Cambridge studying under the logician Max Newman. Newman introduced Turing to Gödel’s recent incompleteness theorem. When he understood Gödel’s result, Turing was able to see how to answer Hilbert’s third question, the Entscheidungsproblem, and his answer, again, was “no.”
How did Turing show this? Remember that the Entscheidungsproblem asks if there is always a “definite procedure” for deciding whether a statement is provable. What does “definite procedure” mean? Turing’s first step was to define this notion. Following the intuition of Leibniz of more than two centuries earlier, Turing formulated his definition by thinking about a powerful calculating machine—one that could not only perform arithmetic but also could manipulate symbols in order to prove mathematical statements. By thinking about how humans might calculate, he constructed a mental design of such a machine, which is now called a Turing machine. The Turing machine turned out to be a blueprint for the invention of the electronic programmable computer.
Alan Turing, 1912–1954 (Photograph copyright ©2003 by Photo Researchers Inc. Reproduced by permission.)
A QUICK INTRODUCTION TO TURING MACHINES
As illustrated in figure 4.1, a Turing machine consists of three parts: (1) A tape, divided into squares (or “cells”), on which symbols can be written and from which symbols can be read. The tape is infinitely long in both directions. (2) A movable read/write tape head that reads symbols from the tape and writes symbols to the tape. At any time, the head is in one of a number of states. (3) A set of rules that tell the head what to do next.
The head starts out at a particular tape cell and in a special start state. At each time step, the head reads the symbol at its current tape cell. The head then follows the rule that corresponds to that symbol and the head’s current state. The rule tells the head what symbol to write on the current tape cell (replacing the previous symbol); whether the head should move to the right, move to the left, or stay put; and what the head’s new state is. When the head goes into a special halt state, the machine is done and stops.
FIGURE 4.1. Illustration of a Turing machine.
The input to the machine is the set of symbols written on the tape before the machine starts. The output from the machine is the set of symbols written on the tape after the machine halts.
A SIMPLE EXAMPLE
A simple example will make all this clearer. To make things really simple, assume that (like a real computer) the only possible symbols that can be on a tape are 0, 1, and a blank symbol indicating a blank tape cell. Let’s design a Turing Machine that reads a tape containing all blank cells except for some number of 1s sandwiched between exactly two 0s (e.g.,