Book tip: Turing’s vision

When I visited New York last year, I picked up a copy of Chris Bernhardt’s book Turing’s Vision: The Birth of Computer Science, which dissects one of Alan Turing’s most interesting papers. I’ve been recommending it to various people since, so I thought I would write about it here.

The book

The book aims to explain a number of complex ideas from computer science and mathematics to the general public. “The reader doesn’t have to understand much mathematics — high school provides enough”, Bernhardt explains.

Personally, I’ve had to skip over bits and pieces, but generally, I’ve found it quite accessible. It takes us back to the historical and philosophical basis for many concepts that are still there in modern-day programming: encoding, regular expressions, Lambda calculus, recursive functions, functions that break on certain input, arrays…

On computable numbers

Turing is well known for his leading role in decrypting messages from the German’s Enigma devices for the allied forces, a history recently turned into a film worth watching. He also came up with the Imitation Game thought experiment to tell humans and computers apart, now known as the ‘Turing test’ (and familiar to all internet users as CAPTCHAs). This book does not focus on those things.

The paper central to this book is called ‘On computable numbers, with an application to the Entscheidungsproblem’. Entscheidungsproblem is German for ‘decision problem’: it is the question whether we can write algorithms that can decide if certain mathematical statements are true or false. The problem was defined by Hilbert, one of the biggest mathematicians of his time. He thought such algorithms did exist. The book goes into various examples of decision problems.

Turing wanted to prove Hilbert wrong. To do this, Turing had to define what an algorithm was; he explained this by breaking complex calculations down into simpler parts. He also defined the very concept of computation, using the concept of ‘Universal Machines’, machines that, he proved, can compute anything that is computable. In 1936, this was all still as theoretical as it gets. We have modern computers now; at the time a computer was the job title of a person hired to do calculations.

Conclusion

Turing’s Vision is quite theoretical, but it is a great read for people who are interested in the early days of computing. It’s a good mix of mathematics, philosophy and computer science, and helps to understand in detail the paper that started it all.

Want to hear more about this book? There’s an interview with the writer (mp3, 8MB).