www.btinternet.com/~adrian.larner/review/knuth
Selected Papers on Computer Science
Donald E. Knuth
CSLI Lecture Notes, no. 59.
1996, 286pp
ISBN 1-881526-91-7
A Review by Adrian Larner for the Computer Journal
This book contains everything Knuth has written on computer science for the non-specialist, that is, “scientists and mathematicians in general, and ... educated people in all fields.” Perfect beach reading for that three month holiday academics get every summer. It covers algorithms (of course), more popular discussions of the interconnections of theory and practice, and historical material from Ancient Babylon to the IBM 650.
It is a lovely read. Knuth’s vision is clear and crisp, because he stands upon a tripod: mathematics, computer science, and software development. He would not claim to have said the last word on the relationships between these disciplines; but it will take a lot of hard thought before anyone can bring us more enlightenment. In this book, he allows us to follow the movements of his own intellect about a number of problems, the giddy shifts between different views: here he is the pure mathematician, there the empirical investigator, here the creator of algorithms, there the analyst of them; and as the solutions come spiralling up out of the mist, their modest discoverer draws our attention to the beauty, or the strangeness, or the sheer unexpectedness to be found in this abstract realm to which he has devoted his professional life.
Here, perhaps, more than in his other writings, we see the author himself revealed. He is a wise man: “software is hard; and it takes a long time.” “nobody should ... be ashamed if they have a secret love for writing computer programs that actually work.” And he is a happy man: “this small idea of mine pleased me so much when I hit on it.” May he live for a hundred years (or he will never finish the great work).
But this is no idle read. (The bit about the beach was a joke.) Knuth compares mathematics to music, to be enjoyed they must be engaged with. So here goes. What is the relationship between an algorithm (an abstract method) and a program that embodies such an algorithm? Or, more simply, what is an algorithm, over and above a program? (Knuth raises the problem in “Chapter 0”.) Perhaps all the really great mathematicians are Platonists: all that beauty could surely not arise from the programs – or, for that matter, the arithmetic – that we create. How could an exquisite, elegant algorithm be merely a chunk of COBOL code?
Solution: we are led astray by wonder. There is an (alas uncomputable) equivalence relationship between programs, “is the same algorithm as”. It is easy to understand informally: programs are the same algorithm if they calculate the same outputs for the same inputs in the same way. (Omit “in the same way” and the relationship becomes “is the same computable function as”.) One should add that a program might be written – or spoken, or merely thought – for something other than a digital computer: explicit instructions for a human calculator would do. With that proviso, anything that is a program is an algorithm, and anything that is an algorithm is a program (ignoring the other uncomputable question, of termination). There are no extra, Platonic, wonder-inducing algorithms over and above the programs: it is just that we can count programs the same if they are the same algorithm, which gives us fewer algorithms than programs (and even fewer computable functions). But not because we are counting additional things.
Of course, that does raise a question about the set of algorithms, which – containing all and only the same things – must be the set of programs (and the set of computable functions): what is its cardinality? Apparently not, as we would have expected, the number of algorithms there are. And that raises the general question: of all the ways to count things, which is the one that gives the cardinality of the set of them?
This, of course, is one of the joys of science: we solve one problem and another one arises. What – in sum – can one say, of our delightful discipline and of this delightful book? Enjoy.
Copyright © 1997, 2001 Adrian Larner. The author asserts all moral rights.
The decorative image of a key (cc004239.gif) used on this page was obtained from IMSI's MasterClips/MasterPhotos© Collection, 1895 Francisco Blvd East, San Rafael, CA 94901-5506, USA.