8.5. Alan Turing 259
Figure 8.1 Alan Turing
Sincen=q 1 < n, this can’t be true, so we conclude thatp 1 < q 1.
Since thepi’s are weakly decreasing, all thepi’s are less thanq 1. But
q 1 jnDp 1 p 2 pj;
so Lemma 8.4.3 implies thatq 1 divides one of thepi’s, which contradicts the fact
thatq 1 is bigger than all them.
8.5 Alan Turing
The man pictured in Figure 8.1 is Alan Turing, the most important figure in the
history of computer science. For decades, his fascinating life story was shrouded
by government secrecy, societal taboo, and even his own deceptions.
At age 24, Turing wrote a paper entitledOn Computable Numbers, with an Ap-
plication to the Entscheidungsproblem. The crux of the paper was an elegant way
to model a computer in mathematical terms. This was a breakthrough, because it
allowed the tools of mathematics to be brought to bear on questions of computation.
For example, with his model in hand, Turing immediately proved that there exist
problems that no computer can solve—no matter how ingenious the programmer.
Turing’s paper is all the more remarkable because he wrote it in 1936, a full decade
