Selected Papers on Computer Science

Donald Knuth is one of the giants of computer science, defining both its practice, through books such as his The Art of Computer Programming, and presentation through the typesetting software T_EX. As the name suggests, Selected Papers on Computer Science is a selection of his papers and lectures. The intended audience for this collection is the general scientific or academic community rather than just computer scientists.

The History of Algorithms

The papers I enjoyed the most were historical ones. The earliest paper in the collection is a short note written in 1966 to Communications of the ACM, arguing that the term “algorithm” should be considered as something distinct from “program”. Specifically, a program is an implementation of an algorithm in a particular language. This distinction is important as it defines one of the main objects of study in computer science as something more intrinsic than a program. Although he doesn’t say it explicitly, algorithms are essentially what the Church-Turing thesis attempts to pin down.

In Ancient Babylonian Algorithms Knuth relates some of the work that has been done translating and understanding the early procedures for solving problems of volume and area found on 4000 year-old clay tables from what is now called Iraq. Although the Babylonians didn’t have algebra, their working was presented with specific quantities (in base 60) that epitomised the general procedure.

In Von Neumann’s First Computer Program, Knuth translates and analyses the sorting algorithm Von Neumann wrote for the EDVAC. This behemoth of a machine had 2048 32-bit words of working memory and another 64 words of “high-speed” cache. In a proclamation worthy of Bill Gates (though he denies ever saying “640k should be enough for anyone”), Von Neumann declared that this 8k of memory combined with “the almost unlimited capacity of the magnetic tape … it seems that very few problems would exceed this capacity”.

Twelve years later, at age 19, Knuth fell in love with his first computer. The IBM 650: An Appreciation from the Field is a nostalgic look at the machine to which Knuth dedicated The Art of Computer Programming. Despite the IBM 650 not having much more memory than Von Neumann’s EDVAC, Knuth and his colleagues managed to code the SOAP line of compilers for it.

Theory and Practice

The Theory and Practice series of papers show how much this early, hands-on experience influenced Knuth. Even though his analysis of algorithms - the meat and potatoes of TAOCP - has a strong pure mathematical flavour, he’s not afraid of resorting to clever hacks and approximations to squeeze every last ounce of computation power out of a machine. In his 1989 keynote lecture Theory and Practice, IV, he even urges his audience to get down and dirty with their machines and

make a thorough analysis of everything your computer does during one second of computation.

I’ve spent my fair share of time stepping through code in debuggers and I think it’s good for the computer scientist’s soul, but what Knuth is proposing is seriously hardcore.

What Can Be Automated?

From a philosophical perspective I also enjoyed Knuth’s tribute to George Forsythe, the founder of the Computer Science Division at Standford, pulling in some big names to help him establish the field: Ed Feigenbaum, John McCarthy, Niklaus Wirth, etc.

Importantly, Forsythe managed to beautifully articulate the core question of computer science, arguing

The question “What can be automated?” is one of the most inspiring philosophical and practical questions of contemporary civilization.

I must admit, I experienced one of those heart-stirring moments when that passage leapt from the page and I’ve been rolling around in my mind ever since.

The Verdict

A fascinating personal look at the history and purpose of computer science by one of its pioneers. It’s slightly dry at times but I thoroughly enjoyed it. A must read for anyone who still believes computer science is just a fancy name for programming.