The Essential Knuth

Donald E. Knuth lived two separate lives in the late 1950s. During daylight he ran down the visible and respectable lane of mathematics. During nighttime, he trod the unpaved road of computer programming and compiler writing. Both roads intersected -- as Knuth discovered while reading Noam Chomsky's book Syntactic Structures on his honeymoon in 1961. "Chomsky's theories fascinated me, because they were mathematical yet they could also be understood with my programmer's intuition. It was very curious because otherwise, as a mathematician, I was doing integrals or maybe was learning about Fermat's number theory, but I wasn't manipulating symbols the way I did when I was writing a compiler. With Chomsky, wow, I was actually doing mathematics and computer science simultaneously." How, when, and why did mathematics and computing converge for Knuth? To what extent did logic and Turing machines appear on his radar screen? The early years of convergence ended with the advent of Structured Programming in the late 1960s. How did that affect his later work on TeX? And what did "structure" come to mean to Knuth? Shedding light on where computer science stands today by investigating Knuth's past -- that's what this booklet is about.