Alan Turing wrote at the beginning of the first section of his paper (page 68 of this book) of his definition of computable numbers that “No real attempt will be made to justify the definitions given until we reach §9.” We have now reached Section 9, and the pages that follow have been called by Turing's biographer Andrew Hodges “among the most unusual ever offered in a mathematical paper.”^{1}

Turing will attempt to demonstrate that the capabilities of a Turing Machine are equivalent to a human computer carrying out a well-defined mathematical process. Therefore, if an algorithmic process is insolvable by a Turing Machine, it is also unsolvable by a human. This idea — generally expressed more formally — has come to be known as the Turing thesis or (in a related form) the Church-Turing thesis. It's called a “thesis” because it's much too amorphous a concept to be subjected to a rigorous mathematical proof. The thesis nonetheless extends to other digital computers: Their computational capabilities are no greater than the Turing Machine.

Only the first part of Section 9 appears in this chapter; the remainder requires some background in mathematical logic and will conclude in Part III of this book. For the most part, I will not interrupt Turing's analysis. Here's a summary by Martin Davis:

Turing's “analysis” is a remarkable piece of applied philosophy in which, beginning with a human being carrying out a computation, he proceeds by a process of elimination of ...

Start Free Trial

No credit card required