I was wondering if there are individual publications that have led their authors to win the Turing Prize or if the Turing Prize is the result of a lifetime's work and multiple publications and results.


1 Answer 1


Yes, it happens that the work that merits the Turing award was pioneered or introduced in a single very influential paper. Sometimes, this is even explicitly the reason for the award. For example, in 1976, Rabin and Scott were given the Turing award

For their joint paper "Finite Automata and Their Decision Problem," which introduced the idea of nondeterministic machines, which has proved to be an enormously valuable concept. Their (Scott & Rabin) classic paper has been a continuous source of inspiration for subsequent work in this field.

Similarly, Hartmanis and Stearns won the 1993 Turing award

In recognition of their seminal paper which established the foundations for the field of computational complexity theory.

(The paper contains the original proof of the Time Hierarchy theorem.) Finally, in the blurb for the 2015 Turing award to Diffie and Hellman, a specific paper is mentioned, but it is not the sole reason for the award. The blurb states:

For fundamental contributions to modern cryptography. Diffie and Hellman's groundbreaking 1976 paper, "New Directions in Cryptography,"[44] introduced the ideas of public-key cryptography and digital signatures, which are the foundation for most regularly-used security protocols on the Internet today.

In general, the Turing award looks at widespread impact over a long period (20 years or more). It is more common for this to be over a line of several papers which collectively summarize the impact. For example, the 2018 award to Bengio, Hinton, and LeCun cannot be traced back to a single paper or even two or three, because Neural Networks as we know them today were not defined, optimized, specialized, and engineered successfully all in one paper. Similarly, Barbara Liskov's 2008 award for contributions to programming languages and distributed computing mentions several ideas: "For contributions to practical and theoretical foundations of programming language and system design, especially related to data abstraction, fault tolerance, and distributed computing." Each of the phrases mentioned in the blurb can be traced to a different paper or set of papers.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.