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 ...

Start Free Trial

No credit card required