For my birthday I got, among other things, a copy of The Annotated Turing: A Guided Tour Through Alan Turing’s Historic Paper on Computability and the Turing Machine, by Charles Petzold. I haven’t finished reading it yet, but so far, I highly recommend it; not only that, but I’m pleased to report that I recommend it even for people who don’t have much background in computer science. Petzold does a good job of “setting the stage,” so to speak, describing the necessary mathematical background and context. And so far his explanation of Turing’s paper itself is quite readable and engaging.
Why might you be interested in reading such a thing? Alan Turing is often regarded as the “father of computer science,” and did important foundational work in computer science, mathematics and what we would now call artificial intelligence. His invention of the “Turing machine“—a simple, imaginary machine which serves as a formalization of computation—was an achievement of creative genius that laid the foundations for much of modern computer science. At the same time, it also put to rest one of the biggest open questions in mathematics of his day, the Entscheidungsproblem, whether it was possible to come up with a purely mechanical procedure for determining the truth or falsity of an arbitrary mathematical statement (written down in a suitably formal way). Turing’s surprising answer (also arrived at independently by Alonzo Church, who invented a second important formalization of computation, the lambda-calculus) was no.
In short, if you’re at all curious about some of the brilliant mathematical creativity that went into making possible the machine that you are using at this very moment to read this blog post—you should read The Annotated Turing!