Never Be Bored
1 November 2018
On Computability
The Annotated Turning: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine by Charles Petzold. The Code Book by Simon Singh, Project Euler, Love and Math by Edward Frenkel.
Fair warning: The Annotated Turing by Charles Petzold is heavy on the math. If that's not your thing, you might want to give this a pass. If, however, you are like me a great nerd, I can't recommend this enough. Alan Turning was a gay English mathematician who is now well known as the father of theoretical computer science and for his part in cracking Enigma. Petzold takes us through one of Turing's most famous papers, line by line, paragraph by paragraph.
Axioms are statements that are taken to be true without proof, because they are so fundamental (e.g. x = x for any x). Mathematicians attempt use axioms to prove statements, theorems, using logic, but, as Gödel proved, there exist statements which are impossible to prove given a set of axioms. But what is the method for deciding whether or not a given statement can be proven? Turing's 1936 paper and the subject of this book proved that this question has no answer. Turing showed that there is no general process for deciding whether or not a given statement is provable. In short: some statements cannot be proven, and there is no general process for deciding which statements are unprovable.
Still with me? That's the complicated problem Turing solves, and he does it in a novel way, by describing theoretical computing machines—now known as universal Turing machines. Yup, the first hypothetical computers were used as tools by Turing to solve a mathematics problem. And for more details, you'll just have to read the paper.
My first introduction to Turing was by learning about how he helped crack Enigma, the code machines used by Nazi Germany to encrypt military messages (a neat Numberphile video on that here). For more on that—and a lot more besides, try The Code Book by Simon Singh, which is a bit lighter on the math than The Annotated Turing while still going into technical details. Singh presents a history of codemakers and codebreakers throughout history—the constant and ongoing war between those who try and keep secrets and those that would try to steal them.
Love the idea of the intersection of math and computer science? Then you must check out Project Euler, a website of puzzles. Each problem requires a combination of mathematical and coding background to be able to solve. For example: triangle numbers are the sums of natural numbers, like 10, which is 1+2+3+4, and which has 4 divisors, namely, 1, 2, 4, and 10. What, then, is the first triangle number with over 500 divisors?
If you liked the heavy math of The Annotated Turing, but wanted a bit more of a story, then check out Love and Math by Edward Frenkel. Part passionate ode to the beauty and elegance of mathematics, part autobiography, this book made me want to be a theoretical mathematician. From his account of his early education in Russia to Fermat's last theorem to the Langlands Program, Frenkel has such a genuine love for math that shows.