Elusive Turing

Today is the centenary of the birth of Alan Turing [1912-1954]. He is represented in Manchester by this park-bench sculpture, which includes the cyanide-laced apple that killed the genius.

Google has celebrated the centenary by creating an ingenious doodle representing a Turing machine, but it takes some time and effort to figure out what it's supposed to do.

In my earlier blog post entitled Turing that unknown [display], I suggested that it's not easy to grasp what exactly Turing achieved. Fortunately, the US computer-science author Charles Petzold has offered us an excellent book, The Annotated Turing, which explains precisely the achievements of Turing.

While it's true that Turing's contribution to the British war effort at Bletchley Park was invaluable, his achievements in code-breaking were not the reason why we consider Turing today as the patriarch of computing. Likewise, while we appreciate Turing's suggestion about considering convincing man/machine conversations as a criterion for so-called artificial intelligence, this too was not really an all-important factor in Turing's claim to fame. So, why is Turing so greatly admired by computer scientists?

Well, his invention of the abstract concept of a so-called Turing machine (like the one in the Google doodle) threw light upon the limitations of algorithmic devices such as computers. More precisely, to use a horrible German term, Turing demonstrated that the Entscheidungsproblem cannot be solved. And what is this exotic beast? You might call it the "mission accomplished" problem. Like George W Bush with his war games, computers will remain forever incapable of determining beforehand whether or not a certain computing challenge can indeed be handled successfully. Turing taught us that the only way of knowing whether or not a computer can handle such-and-such a complex challenge is to set the machine into action and see whether or not it soon halts with a solution.

You might say that Turing proved that the proof of the computer pudding is in the computing.