I want to recount a moment in math history, of the great Alan Turing's 1936 contribution to computer science and mathematical logic -- a great, geeky triumph. I hope to share a glimpse of the elegance and beauty found in Turing's proof, being neither too technical nor too vague. I warn you, it's a nerdy topic from long ago, and I've added opinionated blather about history and math as a non-historian and non-mathematician; but I welcome correction and dissent in the comments.
Tell me, O Muse, of that ingenious hero, who thought long and hard on how Hilbert's question to destroy.
I suppose every century is full of upheaval, but the early twentieth might deserve some special infamy for destruction, disillusionment and angst, at least in Europe. We all know of the bellicose politics and volatile economies, but even in academe, mathematicians and scientists were shaken by new developments. In 1905, Einstein published an amazing quartet of papers that led to a critical rethinking of the characteristics of time, space, matter, and energy. Quantum mechanics emerged in this period, and made natural philosophers doubt the particularity of particles and the innocence of observation. Science of the late nineteenth century had been bursting with confidence, but it stumbled in the new century. Bertrand Russell and A. N. Whitehead composed Principia Mathematica, a monumental treatise on the logical foundations of mathematics, intended to serve as a bedrock on which all mathematical truth could rest. That hope was soon curdled by a young Austrian logician named Gödel. David Hilbert's optimistic motto (later, his epitaph) had been "We must know! We will know!" In 1900 he famously presented ten grand-challenge style unsolved mathematical problems to inspire a new generation of mathematical research. One of them evolved into what I call the Great Decision Problem, whose downfall this story tells. Even for the very privileged, it was a troubling time.
Into this turbulence, whilst the shock waves of the sinking Titanic were almost still rippling across the English main, Alan Mathison Turing was born. I'm devoting a separate diary to tell his story, and this is a companion piece to recount one of his great accomplishments. For now it may be enough to describe him as a fiercely independent thinker who was passionate about science, deeply intelligent, and often at odds with convention. Somehow he survived English public school and won a scholarship to Cambridge. First as an undergraduate, then as a Fellow, he studied mathematics both pure and applied. Influenced by a graduate seminar in 1935 on mathematical logic, he chose to tackle one of Hilbert's grand-challenge problems, the Great Decision Problem (more properly known as the Entscheidungsproblem).
Read More