a story lives forever
Sign in
Form submission failed!

Stay signed in

Recover your password?
Form submission failed!

Web of Stories Ltd would like to keep you informed about our products and services.

Please tick here if you would like us to keep you informed about our products and services.

I have read and accepted the Terms & Conditions.

Please note: Your email and any private information provided at registration will not be passed on to other individuals or organisations without your specific approval.

Video URL

You must be registered to use this feature. Sign in or register.


Getting my PhD and the problem of symmetric block designs with lambda equals two


My interest in context-free languages
Donald Knuth Scientist
Comments (0) Please sign in or register to add comments

I had no idea that that work connected with mathematics in any way whatsoever. They… I wear one cap in the computer… when I'm consulting for Burroughs, and I wear another cap when I'm at Caltech as a student learning mathematics. Mathematics was something where we proved things correct; we knew what we were… you know, we knew what the rules of the game were. In the computer field, we just fiddled with something until it seemed to work and we couldn't find any errors any more. But we never had this… this idea that it could be mathematically correct. The only small exception to that was the… the area of syntax of… of programming languages. This means the grammar of languages.
I mentioned that when I was in seventh grade my friends and I loved grammar, and we… and we learned about English grammar. Well, now I was seeing the same kind of things, you know, not nouns and verbs, but similar things in the algebraic languages like ALGOL, that I was supposed to write software for, and a… and a theory had been developing called the theory of context-free languages that was appealing to me, because here was something that I could be… I… I could use my mathematical cap and my computer cap at sort of the same time. I… you know, my computer science intuition, and my love of grammar and language was… suggested interesting problems, the mathematics that I knew suggested how to solve those problems. So I… I… that was one thing where the… where the two worlds, the computing and the… and the math world, were… were coming together for me. And… and I have to say that on my honeymoon, when… when Jill and I sailed to Europe, I brought along with me [a] book by Noam Chomsky, which was one of the… the pioneering things about… about context-free languages, and I… and I read that in odd moments, you know, when Jill was seasick or something, and… and I would… and I would try to solve the problem about context-free languages.

The problem I tried to solve was, is there a… a way to test whether a context-free grammar is ambiguous or not? Ambiguous means that you could write a sentence that had two different ways to be understood. And… and I thought I… I might have a way to… to resolve this, and I… and I reduced it to several other problems, but I couldn't solve the problem, in general, and little beknown, you know… I learned… I learned several years later that in fact three Israeli mathematicians had already proved that the problem had no solution – that there was no way to solve this ambiguity problem, in… in finite time. So… but I didn't know that during my honeymoon, and I just wanted to mention that, although I… I do love Jill, there were also other things that I love too, and one of them was this theory of context-free languages. Another time I guess I should… I have to mention is the time when I… I forgot about one of our dates, and… when I was playing with the computer at Case Tech, but we won't talk about that. But she… she doesn't let me live that one down.

Born in 1938, American computing pioneer Donald Knuth is known for his greatly influential multi-volume work, 'The Art of Computer Programming', his novel 'Surreal Numbers', his invention of TeX and METAFONT electronic publishing tools and his quirky sense of humor.

Listeners: Dikran Karagueuzian

Trained as a journalist, Dikran Karagueuzian is the director of CSLI Publications, publisher of seven books by Donald Knuth. He has known Knuth since the late seventies when Knuth was developing TeX and Metafont, the typesetting and type designing computer programs, respectively.

Tags: Burroughs Corporation, Caltech, Europe, Case Institute of Technology, Noam Chomsky, Jill Knuth

Duration: 3 minutes, 24 seconds

Date story recorded: April 2006

Date story went live: 24 January 2008