What Makes Alan Turing a Great Scientist? -  Introduction to the Special Theme

by Gilles Dowek and Samson Abramsky

This Turing centenary marks a point at which we can realize that Alan Turing has become, with the passage of time, a scientific icon whose name is known by people in many countries world-wide, and far beyond the scientific community. This may seem a paradox because the genesis of computability theory, for which Turing is probably best known, was a collective effort, to which the names of Herbrand, Gödel, Church, Post, Kleene, Rosser and Turing are often associated.

There are of course many non-scientific reasons for Alan Turing to be an icon: his short life, martyrdom, significance as a gay political symbol, ... but Turing's fame came firstly within the scientific community, as a founding father of Computer Science. Thus, for example, it was decided by the ACM, in 1966, to name the highest distinction in computer science, the Turing Award, after him. So we must search for the origin of Turing's fame in his scientific achievements.

Alan Turing started his scientific work with one of the most abstract problems in mathematics: the decision problem. And he solved it by introducing an imaginary, mathematical computing machine. This work already shows the originality of Turing’s work: Church independently solved the decision problem at the same time, but Church's approach focused on the concepts of a language and of an algorithm, with their roots in logic and mathematics. Turing, by contrast, introduced a decisive third concept, of a *machine*, thus going beyond logic, and laying the foundations for the nascent discipline of Computer Science. Moreover, his analysis of computability in terms of his notion of machine was so compelling that it was rapidly accepted as definitive; and in the form of the Church-Turing thesis, is still with us today."