A.M. TURING AWARD WINNERS BY...

United Kingdom – 1980

Additional Materials

Sorting occupied a significant proportion of the computer use in the days of serial files on magnetic tapes and is still of importance today. The key challenge is that the number of comparisons required to sort a collection of things increases exponentially in the number of items. Hoare's Quicksort algorithm was a major advance on the average number of comparisons needed. For more on sorting and, in particular, Quicksort, see here.

**ALGOL 60**

Today there are thousands of programming languages. ALGOL 60 was an early and very influential language designed by members of an IFIP Working Group (WG 2.1) many of whose members became Turing Laureates.

Each type of computer has its own “machine code", and compilers translate so-called “higher level languages" like ALGOL 60 into such machine codes. The correctness of compilers is crucial, and writing them is an exacting task.

For more information on programming languages see here.

**Turing and Reasoning about Programs**

A paper (of which neither Floyd nor Hoare was aware in the 1960s) presented by Turing in Cambridge in 1949 has the seed of Floyd's annotation idea. For more details of this history, see “The Early Search for Tractable Ways of Reasoning about Programs", *IEEE Annals of the History of Computing*, Vol. 25, Num. 2, 2003, pp. 26-49.

The original paper is: A.M. Turing, "Checking a Large Routine," *Report of a Conference on High Speed Automatic Calculating Machines*, Univ. Mathematical Laboratory, Cambridge, UK, June 1949, pp. 67-69. The printed text of Turing's paper contains so many transcription errors that it took considerable effort to decipher. For a corrected version that is also related to later work, see F.L. Morris and C.B. Jones, "An Early Program Proof by Alan Turing," Annals of the History of Computing, Vol. 6, Num. 2, April, 1984, pp. 139-143.

Turing’s paper has also been reprinted in *The Early British Computer Conferences*, Volume 14 in the Charles Babbage Institute Reprint Series, M. Campbell-Kelly and M. R. Williams Editors, MIT Press and Tomash Publishers, 1989.

Tony Hoare was interviewed by Jonathan P. Bowen for the Computer History Museum in 2006. The subjects covered are noted as including:

Logic; Mathematics; Quicksort; Elliott Brothers; Algol 60 compiler; ALGOL; software crisis; Hoare's Logic; Hoare, Sir Antony; Hoare, C.A.R.; Hoare, Tony; Z specification language; CSP concurrent programming model; Parallel computing performance analysis; Fellow Awardee

A transcript of that interview is available here.

National Life Stories in conjunction with British Library shares the transcript of an interview with Sir Tony Hoare conducted by Dr. Thomas Lean here.