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!
I like the idea of the Annotated Turing. I’d like to see more commentaries that explain famous papers in detail and make them accessible to a wider audience. I was predisposed to enjoy the book when I bought it. But it was so tedious that I just couldn’t finish it. Maybe some day when I have more patience I’ll pick it back up.
Happy (belated) birthday!
John: It is a bit tedious in places, but I think partly that’s just the nature of the paper; constructing Turing machines piece by piece can be somewhat tedious. Then again, I think a lot of the details of the actual machine constructions can be skimmed without missing much.
Thanks Annie! =D
I was wondering why my laptop had an infinite tape hanging out the back…now I know! 🙂
(I’ve always been more of a von Neumann man, myself. Plus: Penn pride, man — Turing was at Princeton!)
Oh, whoops. Are Penn and Princeton supposed to be rivals or something? They always forget to tell grad students these sorts of things. =) Anyway, wasn’t von Neumann at Princeton, too?