O'Reilly logo

The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine by Charles Petzold

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

14  The Major Proof

Some mathematical proofs are straightforward; others need to come through the back door. This second category surely includes reductio ad absurdum proofs, which begin by assuming the opposite of what needs to be proven, and then demonstrate that the initial assumption leads to a contradiction.

Then there are the proofs that don't bother coming through the front door or the back door. These proofs instead seem to avoid the subject entirely by building an elaborate structure that at times appears both mysterious and indulgent. Just when the whole point of the exercise has become entirely obscured and you've long since abandoned hopes of ever seeing a solution, the clever mathematician drops through the chimney and exclaims with a hearty “Ta-dah!” that the proof has been completed. (Just don't get any soot on the carpet.)

In a sense, the final section of Turing's paper is the most important part because it is here that he shows that “the Entscheidungsproblem cannot be solved.” This was an important conclusion at the time, but the structure Turing built to support this result — the imaginary device now known as the Turing Machine — ultimately would become more interesting and fruitful than the actual proof that must now command our attention.

Turing laid the foundation for this proof in Section 8. It didn't seem to be very important at the time, but he was careful to establish that you cannot design a Turing Machine that implements a general finite process to determine ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required