The HLF Portraits: Donald Ervin Knuth
No Open Access License:
German copyright law applies. This film may be used for your own use but it may not be distributed via the internet or passed on to external parties.
Knuth, Donald Ervin
The Heidelberg Laureate Forum Foundation presents the HLF Portraits: Donald Ervin Knuth; ACM A.M. Turing Award, 1974 Recipients of the ACM A.M. Turing Award and the Abel Prize in discussion with Marc Pachter, Director Emeritus National Portrait Gallery, Smithsonian Institute, about their lives, their research, their careers and the circumstances that led to the awards. Video interviews produced for the Heidelberg Laureate Forum Foundation by the Berlin photographer Peter Badge. The opinions expressed in this video do not necessarily reflect the views of the Heidelberg Laureate Forum Foundation or any other person or associated institution involved in the making and distribution of the video. Background: The Heidelberg Laureate Forum Foundation (HLFF) annually organizes the Heidelberg Laureate Forum (HLF), which is a networking event for mathematicians and computer scientists from all over the world. The HLFF was established and is funded by the German foundation the Klaus Tschira Stiftung (KTS), which promotes natural sciences, mathematics and computer science. The HLF is strongly supported by the award-granting institutions, the Association for Computing Machinery (ACM: ACM A.M. Turing Award, ACM Prize in Computing), the International Mathematical Union (IMU: Fields Medal, Nevanlinna Prize), and the Norwegian Academy of Science and Letters (DNVA: Abel Prize). The Scientific Partners of the HLFF are the Heidelberg Institute for Theoretical Studies (HITS) and Heidelberg University.
 Music Professor Knuth, I want to begin at the beginning. So can you tell me something about the world into which you were born? I was born in the world of Milwaukee, Wisconsin, and that was 1938, which makes me 78 years old now. And my dad was a well-actioned organist, also a school teacher in the Lutheran school systems. And my mother worked, when I was growing up, during the war, she had a job as a secretary. And then she went on to become involved in real estate in downtown Milwaukee as manager of several buildings. How many children in the family? My sister was born, let's see, three years after me. So there's two of us. Would you say that there were encouragements in particular directions? My parents read every book on how to raise children. And I think with Dr. Spock probably told them what to do. And they decided to actually let me read books, while the common wisdom was to keep that until I was older, because I would then be born in school if I already knew something about it. So the interesting thing was that the Milwaukee Public Library had a bookworm program. And that was the first time I was in the newspaper ever, when I was two years old or something. I was the youngest member of the bookworm club. So I could talk a little more about it, but in those days, children could ride streetcars to downtown Milwaukee safely without the parents there. And I'm not sure how old I was, but I was probably less than ten years old. And I went to the library and took a book and sat by the window. And I didn't know about closing time, and so they had to call my parents. They found me there. My parents had to come and get me out of the library. So they knew that I was, well, I guess the most different thing about me was my long attention span, that I wasn't distracted by something every few months. That's probably the biggest difference between kids now and kids. How much? I understand a bit the role of music in your life a little bit because of the nature of your family and your school, the nature of faith in the early part, although I'd be interested in talking more about that. But what about science and technology in particular? So we didn't have very much about science in my school, but we had very good about grammar, for example, English grammar. So one of the things that fascinated me the most when I was in seventh grade was how to diagram sentences, subject and predicate, and that made sense. We learned something about physiology and so on, but when I get to high school, it would be my first exposure to chemistry. High school really was when you began to... To know something about science that was non-trivial. And the math teachers in high school didn't know that much. But I had a wonderful chemistry and physics teacher in high school. And so there was somebody there to show you the possibilities. Yeah, no. He inspired me greatly. And he wrote his own textbook. So when I... And I said my father was involved with music and I had taken lessons since I was seven years old or something like that. So I continued to draw my interest in music and in high school. For example, I was the accompanist to the chorus. I was in the marching band. I was in the symphonic band. And in one of them I played the saxophone. In one of the other I played the sousaphone. The big one. So then when I came time to go to college, I thought I'd major either in music or in physics. Physics because of the one teacher who inspired me and music because of the other. So you were torn. Well, I was... I mainly considered two different colleges. One of which I would have been a music major and the other which I chose, which was K-Stuck in Cleveland, Ohio, where I started in physics then. I'm not going to let you go to college yet because there's one thing about your childhood through high school that is often referenced in writings about you and that is you're very much of a young problem solver. You're enjoying the idea of solving problems and in some cases in a very witty way solving problems. So can you... Is that fair to describe to you then that you are intrigued by that process? Yeah, but I was also... I was kind of an automaton. I mean, I did what I was told. But I would see things that... And I would play with numbers or... Well, I spent, I don't know how many hours with a little game that has six horses that run around the track and you roll dice and then that tells you how far the horse goes and I would root for the red horse, but I would roll the dice and I would spend hours and hours just watching... Watching the patterns of seeing that some horses actually, even though the fair dice, some horses were actually getting ahead of the others. And my dad had a little calculator, a mechanical calculator that was capable of multiplying ten-digit numbers. And I would run that calculator and I would... I would plot graphs. I suppose I have a function like 3x squared plus 2x minus 5, plus 0.1x cubed or something like this, I would... I spent also hours drawing the graphs as I varied the coefficients of this function and I would see how the graph would change and I filled hundreds of sheets of orange graph paper until my eyes started to hurt. What age are you at this point? I was like a second year in high school, let's say. So clearly you're being recognized by now in your high school as quite able? The thing that... the first time I was recognized was when I was in eighth grade and there was a competition in Milwaukee by the TV station. There was a science show on TV every Saturday morning and the sponsor was Ziegler's Giant Bar Corporation. And the question was, how many words can you make out of the letters in Ziegler's Giant Bar? And so I was very intrigued by this and I feigned stomach ache for two weeks so that I could stay home from school and work on this and find as many words from Ziegler's Giant Bar as I could. And I came up with 4,500 words and the judges had only 2,500 words on it. Yes, astonishing. So instead of problem-solving I would... I guess it's more like obsessive focusing on something. Okay, some would call it a perfectionist or very patient, but obsessive will do. Or just sort of... Determined. Yeah, but doing something completely rather than partway. Right. And this was admired or considered odd? I didn't... I don't know. I just did it. I didn't pay any attention. Right. Which is probably a good lesson in life. So now I can let you go to college and you've decided between physics and music in your college choice. And what was that choice? Where? So I went to K's Tech in Cleveland, Ohio, and that's near my mother's family. She grew up in suburban Cleveland. And the standards of admission were tough and the dean told us the first day that she would look at the guy on our left and on the right. And one of us wouldn't be there next year. So I was... Panic wasn't the right word, but I worked very hard on studying and trying to get... do more work than was assigned for the... for class and things like that. Are you... by the way, did you get a scholarship? I had a scholarship and actually... well, it was a partial scholarship. My parents were not at all well off. Being an organist is not a famous way to make money. No, no, no. But his salary was something like twelve dollars a month when I was born. And he bought this piano over here or rented it. I mean, bought it on... eventually was able to pay it off and... but make a living wage by taking students for piano teaching. Right. In college, we experienced at least two kinds of communities. The communities of fellow students and the communities that the faculty represent in terms of noticing and interacting with. Let's start with the community of students. Was that important, influential in your life in terms of choices? Right. I... well, at first it was just in my dorm, but I would play a lot of ping-pong with the kids and things like that. Until my grades would slip a little bit and then I would have to give up ping-pong bridge and then any other activities. But I joined the school paper and I was a manager for the basketball team. I joined the symphonic band. I was a manager for the track team. So I did lots of extra curricular activities and I also pledged a fraternity in my first year and then became vice president of the fraternity. Yeah. A normal good college experience. Yes. Right. So in other words, I certainly didn't absorb myself fully in my studies, although I did try hard to get those priorities. In terms of faculty mentoring, were there particular individuals who made the difference in your development? Right. My freshman year, I would say that my chemistry teacher knew a lot of chemistry. My physics teacher knew a lot of chemistry and physics and my math teacher knew a lot of mathematics, chemistry and physics. And he was the one that really impressed me. But his main characteristic was that I couldn't impress him. No matter how much I tried, he would just sort of grunt. But I admired him and I wanted him to see that, you know, to say something good about my work and it didn't work. But he was very much, you know, got me to put out and learn a lot of mathematics. Most of it was entirely new to me. I hadn't had in high school. You hadn't had much of a background. In high school, I'd come up with questions that my teachers couldn't answer so I stopped asking. That's very interesting. That's very interesting. So now you have some teachers who can. Not only that, they challenge you. Conversely, in the physics, that was my major, but I found out that I could pass the exams in physics, but I didn't have the intuition. I could answer all the questions, but I didn't know why they asked the questions. So that's a good definition of maybe a moment when you decide this is not for me. Well, that was half of it. The other half was that in physics lab, I was totally inept. I would drop the beakers or whatever. In one of the experiments, we were supposed to measure the heat of, what is it, the specific heat of something. And experimentally, and the answer that I got was so far off that according to the formula in the physics book, I was 220% in error. Wow. And I said, how can anybody be more than 100% wrong? So not only did I know that I was no good at it in the lab, but I also didn't like the way physicists defined percent of error. Yes. I figured they had the wrong formula for percent of error. There was another thing, too. I mean, since I didn't know anything about mathematics when they started, but then I found out that in mathematics, it was possible to have some problems where you actually knew when you had the answer. But I realized that if physics never gets to that state, it's only you get accumulated more and more evidence and things become more and more true. You can never go to the sun and see what's going on there. You can never magnify reality to the point where you know exactly what's there. There's always another layer that's beyond you. And so, you know, the physicist has to go through his whole life with never knowing that he has anything righteous, getting more and more. Sure. Well, that, you know, it's not a bad life, but mathematics has this extra little. So you were welcome to the mathematics faculty. Well, I mean, as a student. Yeah. The other story is that we had this eccentric teacher named Louis Green who had the previous year failed the entire class of civil engineers that he had. And he taught a class for sophomores that he had written the textbook for called basic mathematics. And it talked about logic and things like that. It's now become part of standard curriculum, but he had done it on his own at that time. This was the late 50s. And so he had this reputation for being really brutal. Yeah. I mean, even more than Paul Gunter, who had been my campus teacher. So anyway, Louis gave us this. He touched on a problem one day and he said, you know, if anybody solves this problem, you can automatically in the class. And so naturally, we didn't look at the problem because, you know, if he would give it, it must be hopelessly difficult. Right. But one Saturday morning, I was in the marching band and the band was scheduled to go to Detroit to play a game. And I missed the bus. So I had the whole day, which, you know, which I sort of planned to be just away. And so I said, OK, let me work on Louis Green's impossible problem. And, you know, I was lucky and I solved it. And so on Monday morning, I turned in the answer and he said, OK, you're going to end the class. And so I cut class the rest of the time, you know, I'm busy and the other activity. But then I, but then I fell a little guilty about that afterwards. And so I, in my third year, I became the grader for this class. And so I could make up and learn the stuff that I hadn't learned the previous time. And I switched into being a math major then. And there were five of us for math majors in those days. Now, I'm going to leak just because you have such a rich life. Still need to get you graduated. But I think something quite amazing happened that you didn't just get your BS. The faculty decided to toss in a masters in the process. Yes. How did that come to be? And what had you done? So astonished. Well, this is the fact is, well, I might as well admit it. I found out that it was easy to take grad courses and undergrad courses. Case didn't have as high standards for admitting grad students as undergrad students. And so there's almost no competition. You take a grad course and you can just, it's a breeze. And so, but other students hadn't discovered this yet. So I could take the grad courses and externally it looked like that I was doing more. But it really was, it gave me time to work with the basketball team and the fraternity and so on. Because I didn't have to really work that hard on the grad courses. So then, but Case had a very good press agent, you know, a public relations man. He wanted to get stories in the newspaper. So somehow anyway, I don't know who idea it was, but they made an unprecedented, they had never done it before. Given a master's degree at the same time. And probably not very often after. Yeah, I have no idea. But I was more mostly prominent because of what I did on the basketball team. Because I had computerized, I had figured out a computer program that would rate the basketball players. And this got featured in the Cleveland newspapers and even in CBS Sunday News. And so that got into the paper. And then I was editor of the Science Magazine. Right. Part of my senior year. So the faculty knew that I had been active in extracurricular activities. And so that was, but I think it might have been done mostly as a publicity stunt. It worked for everyone concerned. Okay. Give me a sense of the state of computer science at this point. And by the way, the year of your graduation is 1960. Okay. 1960. What is the state of computer science? Well, I think if even so named, you're right, I think it was probably named in 1962. Okay. Before it's named. Yeah, there was somebody. Yeah, it's probably somebody had had used the word in 15th or something, but it wasn't at all. So, so, all right. So it's a wonderful thing at Case that I happened to be there because there were, I believe, essentially only two universities in the world that trusted undergraduates to do computing. Dartmouth and Case. Really? Yeah. And we had this very enlightened administrator named Fred Way who allowed the, allowed us not only to touch the machines, but to write the software that was used by the rest of the campus. And so, for example, between my second and third year, I worked in the summer at the computer lab with about two dozen other undergraduates. But we wrote a compiler that was used on the campus machine. And I wrote the textbook that was used as a text in my junior course on computing. It sure did. I mean, it wasn't really, the textbook was basically a manual for how to use it. A manual, yes. The user's manual for the compiler. But that was the, that was the text for the course. And so, except, you know, as an undergraduate, he allowed, you know, it wasn't only me. It was a whole bunch of us. So, now you read the cusp of a revolution, whether you know it or not, at this point. And how are you deciding about your next academic stage? Well, there was no connection with, I was a math major, but I had a job as a computer programmer. And I didn't see that those worlds mixed at all. As a computer programmer, I had one set of, you know, you fiddle with your program until it worked, or until you couldn't make it fail. And you tried to squeeze in, the machines were very slow and very small in those times. So, the name of the game mostly was to see how many features, how many things you could accomplish within the limitations of the machine. And so, you know, we got our kicks out of saying that we could make the machine do more tricks than we had believed possible the previous year. But it was the same machine. And on the other hand, in mathematics, we have this tradition of proving that things are correct and much more abstractions. You have axioms that, and you can deduce if A and B are true, then C has to be true and so on. And so, it's a different world entirely. And those worlds didn't join for me until sometime later. So, I didn't know there was a computer world. I mean, I knew that people were using my software. And I also knew that we had some techniques that probably other people could use. And so, there was this magazine sitting around in the computer lab. And I had been writing for newspapers and the student engineering magazine. So, I wrote an article in this for the ACM communications, which was a new publication at the time, explaining the compiler that we had written. However, I had no idea about intellectual property or things. And so, I had only been reading magazine articles and so on, and here's something cool about it. What are the facts? So, this article, I totally didn't even occur to me to mention the names of the other people working on this project. Violation of protocol. But I didn't know there was such protocol. You know, in Time Magazine, you read articles. How old are you, by the way, at this moment? I'm a senior in college. Senior in college. And so, I realized that afterwards that I was getting credit for something that... I expected that I would get the credit for being the journalist or something, but not as the initiator of the idea. What is going to help you decide, again, the next level? Where is your intellectual curiosity taking you? So, the kind of mathematics that I like the most are what's called combinatorial mathematics. It's where you're dealing with things that you can write on pencil and paper, instead of things that are continuously varying as in explosions or differential equations. Much more, you're appealed to me what is the construction of designs and patterns. And so, when I went to... And I had a particularly charismatic teacher, a visitor for the year named Bose, or Raj Chandra...Bose in my senior year, who was inspiring in combinatorial mathematics. And so, he said, well, a good place to go would be Caltech and work with Marshall Hall. And so, that's what I did for graduate. And because of what kind of specialization, what was Caltech going to offer you? The combinatorial mathematics expertise. So, Marshall Hall was one of the...he was just finishing his book on combinatorial mathematics. Would you say at this point in life, as you look to your future, you were expecting to be a theoretical mathematician? I was expecting to be a college teacher. My father was a teacher. When I was in first grade, I wanted to be a first grade teacher, when I was in second grade, I wanted to be a second grade teacher. When I got to college, I wanted to be a college teacher. And I thought maybe I would have a part-time job on the side as an organist like my father had been. That was my plan. So, after you went, Caltech, I'm just guessing he accepted you. Yes. A few when. And again, in a, unfortunately, a short interview, just what becomes the turning point in your intellectual life while you're at Caltech? Right. So, the thing that turns me to computer science is getting to know by correspondence, a guy named Robert Floyd. Bob was also a Turing Award winner later on, but somehow we got to writing it, not to each other. And he was one of the very first people to realize that mathematics can help computer programmers. And so, he said you could prove that a program was correct. You know, not only fiddle with it until it doesn't make mistakes, but you could actually say that it's not going to ever have a mistake again. And this was revolutionary. And I got, and I got to, he also was the best leading person in the field of programming languages and writing compilers. And so, we got into, you know, we met each other at a conference in Syracuse, ACM National Conference in Syracuse in 62, and we hit it off and started writing letters back and forth. And so then, meanwhile, though, I had turned down my fellowships. You turned down your fellowship? I had National Science Foundation fellowship. Yes. But the restriction was that you could not do part-time work. You had to be a full-time student. But really, I was a consultant to Burroughs Corporation. And, you know, because right next to Caltech was the greatest group of compiler writers in the world. And so I got into that group, and so outside of graduate school, I was with them and consulting not only on software but hardware design. Is this a courageous decision? I mean, I'm just interested. This distinguished fellowship offered you something in your gut is telling you, no, don't do that because a better prospect or a more interesting life. Yeah, it's hard for me to remember now, but in a way, it wasn't that. I wasn't ever very strategic. I was more like, you know, I was more like, you know, following water downhill. But there were two things. First of all, I could see that people, there was a great need for people to have better software. And I had this experience in such a case had been so enlightened in developing young people to write software. So I was one of the few people in the world that knew how to write compilers. And, you know, and in fact, the other, you know, big turning point was that January of 62 when a publisher approached me and said, would you write a book on how to write a book? This is a famous moment. So let's stay with this. They come to you and what is it they are expecting, asking you to do? Write a book about compilers and it had lunch with me and it was Addison Wesley representative. And my favorite textbooks throughout undergraduate have been published by Addison Wesley. And so, of course, I was and I had been doing a lot of writing for newspapers and things like that. And so, gosh, this was just clicked. I mean, it was a dream, but I hadn't thought of being an author before, but they presented this to me and I got home and I took a yellow sheet of tablet paper that I still have somewhere. And I chatted down 12 chapters that I thought would be in a book about compilers. And that was, they say that was 1962. So I was in my second year of graduate school. And in the middle of that. By the way, was this compatible with the kind of investment of time that was going to be necessary to get a doctor? Or was that also not a problem for you? I, okay. Somebody had told me when I was very young that you go to grade school for eight years, you go to high school for four years, and then go to college for four years. And then if you want to go further, you go to graduate school for three years. And somebody had told me it took three years to get a PhD. Now, I had that had been planted in me from so so I just had a 12 o'clock. Oh, you're stuck in your case. So I ought to be, you know, I ought to be getting done on graduation day. I looked around and there was only one other guy who had a. You were the only one who had done it in three years. And Al Hales, who also also went on to be quite a mathematician. But anyway, the, the. So it didn't interfere with you again. If this guy had told me that it was going to take five years, I would have done five years. Yeah. But, but you see, I, I'm, the ability to write compilers was all was was rare enough skill that that also it would that it paid for my marriage and my honeymoon. Between my between undergraduate and college, I wrote the, I wrote a compiler and I got paid $5,000 for it. Actually, 5,500. But anyway, that was that that was a lot of money in those days. I mean, yes, yes, more than my father's. And you know, right. And I was starting university professor was $11,000 a year or something like that. Were you getting any advice from mentors at the graduate level about whether or not to take this project on the, the, the Edison Wesley project? No, no, no, no, I, I just. Well, I kept in the back of my mind as something that I would like to do. And I had no idea how, how hard it was going to be. I started to work on it. Now, Caltech asked me during my third year of graduate school, they asked me to teach a class about computers. It's part of the math department offering. And, and, and so I, it for this class, I developed this mythical computer called M I X, which, which, which we're going to be used. And I know I knew I'd be able to use my book. And so, you know, so I was able to develop a few aspects of the book while I was still a graduate student. So there was some compatibility. But, but, but still the, the, the, the mathematical work, the proof and things like that. So the things I did in the math department weren't overlapping with my computer programming and consulting activities very much at all. Now, again, famously, but important to record, I think, again, is what you did with the task of coming up with 12. I'm going to call them neat chapters. I'm sure very complicated chapters. And somehow you didn't manage the 12 chapters. It was not functional to just do 12 chapters. No, no, no, how did that come to be? No, it turned out that that 12 that each chapter, however, became half of a book. I mean, each. So, so the final, the present, the present table of contents for the art of computer programming has still has 12 chapters in it. Oh, yes. But it's not the same order, not the same time. But it's close to volume. But, but, yeah, but, but like chapter seven, for example, is probably going to fill volume for a for B for C, maybe part of for D, because the chapter seven was about combinatorial algorithms and this whole subject exploded. Almost nothing was known in 1962 about combinatorial algorithms. And it's turned out to be immensely important and developed. So, so the word chapter is being misused in my book, actually. Are you essentially the sole author of the multi volume series? Yeah. Called the art of computer programming. Yeah. So you've in a way stumbled into a life. Well, if not an entire life project along. Yeah, a long project. No, it's more than a lifetime project. More than a lifetime project. But I didn't know that. Right, of course, which was probably just as well. Yeah. So now, again, because of the importance of so many things that you've done. So how do you come to master the algorithms? Yeah. Okay, so as I'm working on on the on my okay, so I finished my thesis and then I and then I start which is on what what is the topic thesis was on finite geometries. And so these are these are our beautiful mathematical patterns. Right. It's one of the only parts of mathematics I I've never applied to computer science. Was what you wrote. Yeah. Although it's very beautiful subject. We now know that you're using random techniques. You can do it just as well. So you don't need you don't need all this complication that we had at the time. But still, you know, it it that work is finding applications in studying of tensors and other things now in mathematics. But but it's it's but not applying to computer science. Right. So so I started in earnest to draft chapter on sorting for for it was actually sorting was actually hardly used in in compiler writing. But I thought it would be cool to have a chapter on sorting anyway. And because I had seen that that there was a need for somebody to write about sorting. There were lots of of of uninformed articles out there about it that I'd seen in the literature. So I started working on sorting in it. And all of a sudden I'm able to use my math what I've learned in mathematics to learn about sorting. And and and besides I'm in correspondence with Bob Floyd, who also has good ideas about sorting and mathematics and combinations. So that all of a sudden that then I had this aha moment where I where I where I I saw that by studying a computer method quantitatively instead of qualitatively, I can not only see that work, but I could say that it it worked 13 percent better than this other method. And not just not not only that was better, but that it was that I could quantify exactly how how fast the method was. And and well, actually the aha moment had come in the summer of 62 when I was writing a for-trade compiler. I was in the midst of writing that compiler. One of the things a compiler has to do is is the programmer makes up the name for quantity in his program. And I and the computer has to figure out has to look up that name and see if that name has occurred before. And and and and the the method used in this inside the compiler is called hashing. And so there was a technique that would work in the small computers we had in those days that would work. It would work especially well that that would that would be able to decide what you know what identify somebody has a name, you know, al pha or something like this. And the computer looks it up and says, oh, yeah, that that's something that that I know this is a certain part of your program. So there was there was a hashing method that they had worked, but nobody knew how well it worked. And and there was a rumor that some students at Princeton had worked had tried to solve this problem unsuccessfully. Yeah. But but I took one one day off from writing the compiler because it was kind of tedious working seven days a week, just turning out code. So I spent a day saying, well, let me see if I can figure out how fast hashing goes. And again, I got lucky and and I was able to solve the problem and use the different kind of mathematics and I'd seen before. And so I I wrote a few pages of notes on it. And and then it occurred to me, you know, this could be a lifetime. This could be a lifetime of of of using mathematics to say how good computer algorithms are. So that was really that was really to me the most important change in direction in my life, I would say is most of the evolution of your thought happening principally. And this may not be a question worth answering conversations with yourself or conversation with others. Is it is it mostly a lonely or social inquiry that you're proceeding on in this case? So it's a great question. I I and they say I was mostly just going downhill in those days. But but but I was but also my parents instilled in me this idea of service and teaching. So I also look at it as not a struggle against people, but a struggle against ignorance and to advance advance knowledge and to have something that that other people can use. And and and so so here I have this that you know, I've analyzed this algorithm and I really and I say, well, I, you know, there was a there was a young subject at the time called queuing theory where people had taken a particular kind of algorithm of studying people who are standing in line and figuring out the characteristics of what are what are good ways to service people in line. And that was the only existing algorithm, except a few sorting out that have been analyzed. And so I and so I said, wait, no, here I took hashing and I was able to handle hashing. I was able to analyze that. And and so there must be there must be hundreds of other important algorithms that could be analyzed. And so this could be this could be something that would there would be, you know, really of service to a lot of people if this gave in and to develop this kind of that's wonderful to hear. This is a process. I'm going to ask them general things that of course also have complex answers. But among your other achievements, we all know it, of course, is if you will, the your inquiry into the elegance of type setting in this new form of communication. What set you on that goal? I mean, your achievement of a kind of lasting, both archival and elegant type setting is something that you are much celebrated. How did that come to be? Okay, well, partly I married an artist who could who could introduce me to aesthetics and we took some classes together. And so I got to I got to understand more about that. But you know, it's by Osmosis from my wife, let's say. Yes. Also, as I say, I loved my Edison Wesley textbooks when I was an undergraduate. And they had the only publishing house that had their own their in-house composition and design. The other publishers were were outsourcing it. And so I had I had developed some kind of, you know, just as a reader of books that appealed to me, I had developed a little bit of sense that way. And so when I was approached by us and Wesley to write books, I was thinking, OK, great, I can have my books are going to look just as good too. Then there was a revolution in the type setting world, which went away from metal type. And and no, and and all the people who knew how to do it with the old equipment were dying off and the new machines have not been adapted to mathematics or technical or technical work. And so when I so I had revised my books for the for the second edition of volume two, the proofs came back and made me made me sick because it was just extremely poor. It was it was nowhere near looking like the books had looked before. And and I mean, it was unbelievably bad that the the subscripts were in a different style of type than the than the other parts of a formula and and letters were crooked and blotched. And and really there was so little market for technical type setting that that all the all the publishers had just gone for the their paying customers. So so I was I was in despair until I I happened to see an example of a a book that had been type set on a new kind of machine, which was entirely digital, entirely made of of black and white dots, black dots on a page. And this machine was able to produce books that were that looked like the best of metal type. If if if one just wrote the computer program to decide where the blacks are going and where the whites should go. And and so once they saw that it only took a computer programming in order to solve my problem, then I decided to spend a year figuring out how to write those programs. You know, again, I underestimated and it took 10 years. Something again to a layman who has talked with mathematicians and computer scientists, you're both that it's important, particularly mathematics, to use words and think in elegant terms. The aesthetic phrases that are often used not so much by computer scientists, but certainly seems to me that search for elegance seem to have informed not only your intellectual background, but your visual background in in your contributions to computers. Is that fair to say? Well, the the aesthetic notion of beauty is inherent to to mathematics as well as and I I one of the reasons I call my book the art of computer programming was because it has some aesthetic art. Exactly, it has some something about the beauty in it as well. In your continued years, because we can't really explore them at Stanford, which is of course, very important part of your life. I think you wound up with a title which the art of computing is inherent in the title there must be the only one in the world. No, I don't think so. No, well, if it exists, it's because you. Well, but anyway, my touring lecture was actually about computer programming as an art, or it's the title. And I addressed the question there, what does the word art mean? And what does it mean when you say something as an art and not a science? There's all kinds of famous things like, you know, it's clever, but is it art and so on. But the word really means is really more close to artisan and artificial. Artisan, yes. Artificial. It means it means something that's not in nature, something that human beings have added to the natural world. But then, I mean, in German, the same word. But then it often means then the fine arts and connects to this, these ideas of elegance and beauty. But really, it mostly means something that's not in the natural world. I see. So the beauty's incidental. It's what we added on though. Another very broad question I wanted to ask you, and you've had other people wonder at this before, is how faith operates in your life which is compatible to that of a mathematician and computer scientist. And you've actually written about this. Is it unusual in your field and profession to welcome faith as well as science? Yeah, well, it's hard to say that people don't broadcast this very much. But in the academic world, there are more people who broadcast their lack of faith, I wouldn't say. And so I had this great opportunity when people at MIT asked me if I would come in 1999 and give a series of lectures that would talk about the relations between faith and science. And this was the second or third year of a program that they had had. But this year, they wanted, in the previous years, they had just had guest lectures about a bunch of people. But this time, I was supposed to do all six. And so I figured, well, what better, if I was ever going to do something like this, what better place to do it than Boston at MIT because they had also all these great theological schools around there and Harvard and where I had spent some time. So I couldn't resist the temptation. Of course. I wanted to. It's an elegant invitation. But yeah. So then I gave these lectures. And the lectures were hour and a half each and about 30 minutes of that I prepared and an hour where I would just answer the questions of all the people in the audience that cover the whole thing. So this was transcribed into a book and people couldn't look at it. But the way I overall, in general, I think, well, computer science is wonderful, mathematics is wonderful, but it's not everything. And as I said, I like the fact that with mathematics, I could get to different answers. But I also am happy that there are things that are beyond my ken and questions that I'll never know the answers to, but mysteries that I can learn more and more about. I wouldn't be happy if everything was a mystery, but I'm also not happy if nothing is a mystery. Maybe that's a way to think about it that in some ways in science, modern science, there's an intolerance of mystery or a kind of irritation with mystery. And hubris, once we've solved something, then we can solve everything. And so I find the opposite. When I learn something new, then I also learn more that I don't know.
 Music  Professor Knuth, I want to begin at the beginning.  So can you tell me something about the world into which you were born?  I was born in the world of Milwaukee, Wisconsin, and that was 1938, which makes me 78 years old now.  And my dad was a well-actioned organist, also a school teacher in the Lutheran school systems.  And my mother worked, when I was growing up, during the war, she had a job as a secretary.  And then she went on to become involved in real estate in downtown Milwaukee as manager of several buildings.  How many children in the family?  My sister was born, let's see, three years after me. So there's two of us.  Would you say that there were encouragements in particular directions?  My parents read every book on how to raise children.  And I think with Dr. Spock probably told them what to do.  And they decided to actually let me read books, while the common wisdom was to keep that until I was older,  because I would then be born in school if I already knew something about it.  So the interesting thing was that the Milwaukee Public Library had a bookworm program.  And that was the first time I was in the newspaper ever, when I was two years old or something.  I was the youngest member of the bookworm club.  So I could talk a little more about it, but in those days, children could ride streetcars to downtown Milwaukee safely without the parents there.  And I'm not sure how old I was, but I was probably less than ten years old.  And I went to the library and took a book and sat by the window.  And I didn't know about closing time, and so they had to call my parents.  They found me there.  My parents had to come and get me out of the library.  So they knew that I was, well, I guess the most different thing about me was my long attention span,  that I wasn't distracted by something every few months.  That's probably the biggest difference between kids now and kids.  How much? I understand a bit the role of music in your life a little bit because of the nature of your family and your school,  the nature of faith in the early part, although I'd be interested in talking more about that.  But what about science and technology in particular?  So we didn't have very much about science in my school, but we had very good about grammar, for example, English grammar.  So one of the things that fascinated me the most when I was in seventh grade was how to diagram sentences,  subject and predicate, and that made sense.  We learned something about physiology and so on, but when I get to high school, it would be my first exposure to chemistry.  High school really was when you began to...  To know something about science that was non-trivial.  And the math teachers in high school didn't know that much.  But I had a wonderful chemistry and physics teacher in high school.  And so there was somebody there to show you the possibilities.  Yeah, no. He inspired me greatly.  And he wrote his own textbook.  So when I... And I said my father was involved with music and I had taken lessons since I was seven years old or something like that.  So I continued to draw my interest in music and in high school.  For example, I was the accompanist to the chorus.  I was in the marching band. I was in the symphonic band.  And in one of them I played the saxophone.  In one of the other I played the sousaphone.  The big one.  So then when I came time to go to college,  I thought I'd major either in music or in physics.  Physics because of the one teacher who inspired me and music because of the other.  So you were torn.  Well, I was... I mainly considered two different colleges.  One of which I would have been a music major and the other which I chose,  which was K-Stuck in Cleveland, Ohio, where I started in physics then.  I'm not going to let you go to college yet because there's one thing about your childhood through high school  that is often referenced in writings about you and that is you're very much of a young problem solver.  You're enjoying the idea of solving problems and in some cases in a very witty way solving problems.  So can you... Is that fair to describe to you then that you are intrigued by that process?  Yeah, but I was also... I was kind of an automaton.  I mean, I did what I was told.  But I would see things that...  And I would play with numbers or...  Well, I spent, I don't know how many hours with a little game that has six horses that run around the track  and you roll dice and then that tells you how far the horse goes  and I would root for the red horse, but I would roll the dice and I would spend hours and hours just watching...  Watching the patterns of seeing that some horses actually, even though the fair dice,  some horses were actually getting ahead of the others.  And my dad had a little calculator, a mechanical calculator that was capable of multiplying ten-digit numbers.  And I would run that calculator and I would...  I would plot graphs.  I suppose I have a function like 3x squared plus 2x minus 5,  plus 0.1x cubed or something like this, I would... I spent also hours drawing the graphs  as I varied the coefficients of this function and I would see how the graph would change  and I filled hundreds of sheets of orange graph paper until my eyes started to hurt.  What age are you at this point?  I was like a second year in high school, let's say.  So clearly you're being recognized by now in your high school as quite able?  The thing that... the first time I was recognized was when I was in eighth grade  and there was a competition in Milwaukee by the TV station.  There was a science show on TV every Saturday morning  and the sponsor was Ziegler's Giant Bar Corporation.  And the question was, how many words can you make out of the letters in Ziegler's Giant Bar?  And so I was very intrigued by this  and I feigned stomach ache for two weeks so that I could stay home from school  and work on this and find as many words from Ziegler's Giant Bar as I could.  And I came up with 4,500 words and the judges had only 2,500 words on it.  Yes, astonishing.  So instead of problem-solving I would... I guess it's more like obsessive focusing on something.  Okay, some would call it a perfectionist or very patient, but obsessive will do.  Or just sort of...  Determined.  Yeah, but doing something completely rather than partway.  Right. And this was admired or considered odd?  I didn't... I don't know. I just did it. I didn't pay any attention.  Right. Which is probably a good lesson in life.  So now I can let you go to college and you've decided between physics and music in your college choice.  And what was that choice? Where?  So I went to K's Tech in Cleveland, Ohio, and that's near my mother's family.  She grew up in suburban Cleveland.  And the standards of admission were tough and the dean told us the first day that she would look at the guy on our left and on the right.  And one of us wouldn't be there next year.  So I was... Panic wasn't the right word, but I worked very hard on studying and trying to get... do more work than was assigned for the... for class and things like that.  Are you... by the way, did you get a scholarship?  I had a scholarship and actually... well, it was a partial scholarship.  My parents were not at all well off.  Being an organist is not a famous way to make money.  No, no, no. But his salary was something like twelve dollars a month when I was born.  And he bought this piano over here or rented it.  I mean, bought it on... eventually was able to pay it off and... but make a living wage by taking students for piano teaching.  Right.  In college, we experienced at least two kinds of communities.  The communities of fellow students and the communities that the faculty represent in terms of noticing and interacting with.  Let's start with the community of students.  Was that important, influential in your life in terms of choices?  Right.  I... well, at first it was just in my dorm, but I would play a lot of ping-pong with the kids and things like that.  Until my grades would slip a little bit and then I would have to give up ping-pong bridge and then any other activities.  But I joined the school paper and I was a manager for the basketball team.  I joined the symphonic band. I was a manager for the track team.  So I did lots of extra curricular activities and I also pledged a fraternity in my first year and then became vice president of the fraternity.  Yeah.  A normal good college experience.  Yes.  Right.  So in other words, I certainly didn't absorb myself fully in my studies, although I did try hard to get those priorities.  In terms of faculty mentoring, were there particular individuals who made the difference in your development?  Right.  My freshman year, I would say that my chemistry teacher knew a lot of chemistry.  My physics teacher knew a lot of chemistry and physics and my math teacher knew a lot of mathematics, chemistry and physics.  And he was the one that really impressed me.  But his main characteristic was that I couldn't impress him.  No matter how much I tried, he would just sort of grunt.  But I admired him and I wanted him to see that, you know, to say something good about my work and it didn't work.  But he was very much, you know, got me to put out and learn a lot of mathematics.  Most of it was entirely new to me.  I hadn't had in high school.  You hadn't had much of a background.  In high school, I'd come up with questions that my teachers couldn't answer so I stopped asking.  That's very interesting.  That's very interesting.  So now you have some teachers who can.  Not only that, they challenge you.  Conversely, in the physics, that was my major, but I found out that I could pass the exams in physics, but I didn't have the intuition.  I could answer all the questions, but I didn't know why they asked the questions.  So that's a good definition of maybe a moment when you decide this is not for me.  Well, that was half of it.  The other half was that in physics lab, I was totally inept.  I would drop the beakers or whatever.  In one of the experiments, we were supposed to measure the heat of, what is it, the specific heat of something.  And experimentally, and the answer that I got was so far off that according to the formula in the physics book, I was 220% in error.  Wow.  And I said, how can anybody be more than 100% wrong?  So not only did I know that I was no good at it in the lab, but I also didn't like the way physicists defined percent of error.  Yes.  I figured they had the wrong formula for percent of error.  There was another thing, too. I mean, since I didn't know anything about mathematics when they started, but then I found out that in mathematics, it was possible to have some problems where you actually knew when you had the answer.  But I realized that if physics never gets to that state, it's only you get accumulated more and more evidence and things become more and more true.  You can never go to the sun and see what's going on there. You can never magnify reality to the point where you know exactly what's there.  There's always another layer that's beyond you.  And so, you know, the physicist has to go through his whole life with never knowing that he has anything righteous, getting more and more.  Sure. Well, that, you know, it's not a bad life, but mathematics has this extra little.  So you were welcome to the mathematics faculty.  Well, I mean, as a student.  Yeah. The other story is that we had this eccentric teacher named Louis Green who had the previous year failed the entire class of civil engineers that he had.  And he taught a class for sophomores that he had written the textbook for called basic mathematics.  And it talked about logic and things like that.  It's now become part of standard curriculum, but he had done it on his own at that time.  This was the late 50s.  And so he had this reputation for being really brutal.  Yeah. I mean, even more than Paul Gunter, who had been my campus teacher.  So anyway, Louis gave us this.  He touched on a problem one day and he said, you know, if anybody solves this problem, you can automatically in the class.  And so naturally, we didn't look at the problem because, you know, if he would give it, it must be hopelessly difficult.  Right.  But one Saturday morning, I was in the marching band and the band was scheduled to go to Detroit to play a game.  And I missed the bus.  So I had the whole day, which, you know, which I sort of planned to be just away.  And so I said, OK, let me work on Louis Green's impossible problem.  And, you know, I was lucky and I solved it.  And so on Monday morning, I turned in the answer and he said, OK, you're going to end the class.  And so I cut class the rest of the time, you know, I'm busy and the other activity.  But then I, but then I fell a little guilty about that afterwards.  And so I, in my third year, I became the grader for this class.  And so I could make up and learn the stuff that I hadn't learned the previous time.  And I switched into being a math major then.  And there were five of us for math majors in those days.  Now, I'm going to leak just because you have such a rich life.  Still need to get you graduated.  But I think something quite amazing happened that you didn't just get your BS.  The faculty decided to toss in a masters in the process.  Yes.  How did that come to be?  And what had you done?  So astonished.  Well, this is the fact is, well, I might as well admit it.  I found out that it was easy to take grad courses and undergrad courses.  Case didn't have as high standards for admitting grad students as undergrad students.  And so there's almost no competition.  You take a grad course and you can just, it's a breeze.  And so, but other students hadn't discovered this yet.  So I could take the grad courses and externally it looked like that I was doing more.  But it really was, it gave me time to work with the basketball team and the fraternity and so on.  Because I didn't have to really work that hard on the grad courses.  So then, but Case had a very good press agent, you know, a public relations man.  He wanted to get stories in the newspaper.  So somehow anyway, I don't know who idea it was, but they made an unprecedented, they had never done it before.  Given a master's degree at the same time.  And probably not very often after.  Yeah, I have no idea.  But I was more mostly prominent because of what I did on the basketball team.  Because I had computerized, I had figured out a computer program that would rate the basketball players.  And this got featured in the Cleveland newspapers and even in CBS Sunday News.  And so that got into the paper.  And then I was editor of the Science Magazine.  Right.  Part of my senior year.  So the faculty knew that I had been active in extracurricular activities.  And so that was, but I think it might have been done mostly as a publicity stunt.  It worked for everyone concerned.  Okay.  Give me a sense of the state of computer science at this point.  And by the way, the year of your graduation is 1960.  Okay.  1960.  What is the state of computer science?  Well, I think if even so named, you're right, I think it was probably named in 1962.  Okay.  Before it's named.  Yeah, there was somebody.  Yeah, it's probably somebody had had used the word in 15th or something, but it wasn't at all.  So, so, all right.  So it's a wonderful thing at Case that I happened to be there because there were, I believe,  essentially only two universities in the world that trusted undergraduates to do computing.  Dartmouth and Case.  Really?  Yeah.  And we had this very enlightened administrator named Fred Way who allowed the,  allowed us not only to touch the machines, but to write the software that was used by the rest of the campus.  And so, for example, between my second and third year, I worked in the summer at the computer lab with about two dozen other undergraduates.  But we wrote a compiler that was used on the campus machine.  And I wrote the textbook that was used as a text in my junior course on computing.  It sure did.  I mean, it wasn't really, the textbook was basically a manual for how to use it.  A manual, yes.  The user's manual for the compiler.  But that was the, that was the text for the course.  And so, except, you know, as an undergraduate, he allowed, you know, it wasn't only me.  It was a whole bunch of us.  So, now you read the cusp of a revolution, whether you know it or not, at this point.  And how are you deciding about your next academic stage?  Well, there was no connection with, I was a math major, but I had a job as a computer programmer.  And I didn't see that those worlds mixed at all.  As a computer programmer, I had one set of, you know, you fiddle with your program until it worked,  or until you couldn't make it fail.  And you tried to squeeze in, the machines were very slow and very small in those times.  So, the name of the game mostly was to see how many features, how many things you could accomplish  within the limitations of the machine.  And so, you know, we got our kicks out of saying that we could make the machine do more tricks  than we had believed possible the previous year.  But it was the same machine.  And on the other hand, in mathematics, we have this tradition of proving that things are correct  and much more abstractions.  You have axioms that, and you can deduce if A and B are true, then C has to be true and so on.  And so, it's a different world entirely.  And those worlds didn't join for me until sometime later.  So, I didn't know there was a computer world.  I mean, I knew that people were using my software.  And I also knew that we had some techniques that probably other people could use.  And so, there was this magazine sitting around in the computer lab.  And I had been writing for newspapers and the student engineering magazine.  So, I wrote an article in this for the ACM communications, which was a new publication at the time,  explaining the compiler that we had written.  However, I had no idea about intellectual property or things.  And so, I had only been reading magazine articles and so on, and here's something cool about it.  What are the facts?  So, this article, I totally didn't even occur to me to mention the names of the other people working on this project.  Violation of protocol. But I didn't know there was such protocol.  You know, in Time Magazine, you read articles.  How old are you, by the way, at this moment?  I'm a senior in college.  Senior in college.  And so, I realized that afterwards that I was getting credit for something that...  I expected that I would get the credit for being the journalist or something, but not as the initiator of the idea.  What is going to help you decide, again, the next level?  Where is your intellectual curiosity taking you?  So, the kind of mathematics that I like the most are what's called combinatorial mathematics.  It's where you're dealing with things that you can write on pencil and paper,  instead of things that are continuously varying as in explosions or differential equations.  Much more, you're appealed to me what is the construction of designs and patterns.  And so, when I went to...  And I had a particularly charismatic teacher, a visitor for the year named Bose,  or Raj Chandra...Bose in my senior year, who was inspiring in combinatorial mathematics.  And so, he said, well, a good place to go would be Caltech and work with Marshall Hall.  And so, that's what I did for graduate.  And because of what kind of specialization, what was Caltech going to offer you?  The combinatorial mathematics expertise.  So, Marshall Hall was one of the...he was just finishing his book on combinatorial mathematics.  Would you say at this point in life, as you look to your future, you were expecting to be a theoretical mathematician?  I was expecting to be a college teacher.  My father was a teacher.  When I was in first grade, I wanted to be a first grade teacher,  when I was in second grade, I wanted to be a second grade teacher.  When I got to college, I wanted to be a college teacher.  And I thought maybe I would have a part-time job on the side as an organist like my father had been.  That was my plan.  So, after you went, Caltech, I'm just guessing he accepted you.  Yes.  A few when.  And again, in a, unfortunately, a short interview, just what becomes the turning point in your intellectual life while you're at Caltech?  Right.  So, the thing that turns me to computer science is getting to know by correspondence, a guy named Robert Floyd.  Bob was also a Turing Award winner later on, but somehow we got to writing it, not to each other.  And he was one of the very first people to realize that mathematics can help computer programmers.  And so, he said you could prove that a program was correct.  You know, not only fiddle with it until it doesn't make mistakes, but you could actually say that it's not going to ever have a mistake again.  And this was revolutionary.  And I got, and I got to, he also was the best leading person in the field of programming languages and writing compilers.  And so, we got into, you know, we met each other at a conference in Syracuse, ACM National Conference in Syracuse in 62, and we hit it off and started writing letters back and forth.  And so then, meanwhile, though, I had turned down my fellowships.  You turned down your fellowship?  I had National Science Foundation fellowship.  Yes.  But the restriction was that you could not do part-time work.  You had to be a full-time student.  But really, I was a consultant to Burroughs Corporation.  And, you know, because right next to Caltech was the greatest group of compiler writers in the world.  And so I got into that group, and so outside of graduate school, I was with them and consulting not only on software but hardware design.  Is this a courageous decision?  I mean, I'm just interested.  This distinguished fellowship offered you something in your gut is telling you, no, don't do that because a better prospect or a more interesting life.  Yeah, it's hard for me to remember now, but in a way, it wasn't that.  I wasn't ever very strategic.  I was more like, you know, I was more like, you know, following water downhill.  But there were two things.  First of all, I could see that people, there was a great need for people to have better software.  And I had this experience in such a case had been so enlightened in developing young people to write software.  So I was one of the few people in the world that knew how to write compilers.  And, you know, and in fact, the other, you know, big turning point was that January of 62 when a publisher approached me and said,  would you write a book on how to write a book?  This is a famous moment.  So let's stay with this.  They come to you and what is it they are expecting, asking you to do?  Write a book about compilers and it had lunch with me and it was Addison Wesley representative.  And my favorite textbooks throughout undergraduate have been published by Addison Wesley.  And so, of course, I was and I had been doing a lot of writing for newspapers and things like that.  And so, gosh, this was just clicked.  I mean, it was a dream, but I hadn't thought of being an author before, but they presented this to me and I got home and I took a yellow sheet of tablet paper that I still have somewhere.  And I chatted down 12 chapters that I thought would be in a book about compilers.  And that was, they say that was 1962.  So I was in my second year of graduate school.  And in the middle of that.  By the way, was this compatible with the kind of investment of time that was going to be necessary to get a doctor?  Or was that also not a problem for you?  I, okay.  Somebody had told me when I was very young that you go to grade school for eight years, you go to high school for four years, and then go to college for four years.  And then if you want to go further, you go to graduate school for three years.  And somebody had told me it took three years to get a PhD.  Now, I had that had been planted in me from so so I just had a 12 o'clock.  Oh, you're stuck in your case.  So I ought to be, you know, I ought to be getting done on graduation day.  I looked around and there was only one other guy who had a.  You were the only one who had done it in three years.  And Al Hales, who also also went on to be quite a mathematician.  But anyway, the, the.  So it didn't interfere with you again.  If this guy had told me that it was going to take five years, I would have done five years.  Yeah.  But, but you see, I, I'm, the ability to write compilers was all was was rare enough skill that that also it would that it paid for my marriage and my honeymoon.  Between my between undergraduate and college, I wrote the, I wrote a compiler and I got paid $5,000 for it.  Actually, 5,500.  But anyway, that was that that was a lot of money in those days.  I mean, yes, yes, more than my father's.  And you know, right.  And I was starting university professor was $11,000 a year or something like that.  Were you getting any advice from mentors at the graduate level about whether or not to take this project on the, the, the Edison Wesley project?  No, no, no, no, I, I just.  Well, I kept in the back of my mind as something that I would like to do.  And I had no idea how, how hard it was going to be.  I started to work on it.  Now, Caltech asked me during my third year of graduate school, they asked me to teach a class about computers.  It's part of the math department offering.  And, and, and so I, it for this class, I developed this mythical computer called M I X, which, which, which we're going to be used.  And I know I knew I'd be able to use my book. And so, you know, so I was able to develop a few aspects of the book while I was still a graduate student.  So there was some compatibility.  But, but, but still the, the, the, the mathematical work, the proof and things like that.  So the things I did in the math department weren't overlapping with my computer programming and consulting activities very much at all.  Now, again, famously, but important to record, I think, again, is what you did with the task of coming up with 12.  I'm going to call them neat chapters.  I'm sure very complicated chapters.  And somehow you didn't manage the 12 chapters.  It was not functional to just do 12 chapters.  No, no, no, how did that come to be?  No, it turned out that that 12 that each chapter, however, became half of a book.  I mean, each. So, so the final, the present, the present table of contents for the art of computer programming has still has 12 chapters in it.  Oh, yes.  But it's not the same order, not the same time.  But it's close to volume.  But, but, yeah, but, but like chapter seven, for example, is probably going to fill volume for a for B for C, maybe part of for D, because the chapter seven was about combinatorial algorithms and this whole subject exploded.  Almost nothing was known in 1962 about combinatorial algorithms.  And it's turned out to be immensely important and developed.  So, so the word chapter is being misused in my book, actually.  Are you essentially the sole author of the multi volume series?  Yeah.  Called the art of computer programming.  Yeah.  So you've in a way stumbled into a life. Well, if not an entire life project along.  Yeah, a long project.  No, it's more than a lifetime project.  More than a lifetime project.  But I didn't know that.  Right, of course, which was probably just as well.  Yeah.  So now, again, because of the importance of so many things that you've done.  So how do you come to master the algorithms?  Yeah.  Okay, so as I'm working on on the on my okay, so I finished my thesis and then I and then  I start which is on what what is the topic thesis was on finite geometries.  And so these are these are our beautiful mathematical patterns.  Right.  It's one of the only parts of mathematics I I've never applied to computer science.  Was what you wrote.  Yeah.  Although it's very beautiful subject. We now know that you're using random techniques.  You can do it just as well.  So you don't need you don't need all this complication that we had at the time.  But still, you know, it it that work is finding applications in studying of tensors and other  things now in mathematics.  But but it's it's but not applying to computer science.  Right.  So so I started in earnest to draft chapter on sorting for for it was actually sorting  was actually hardly used in in compiler writing.  But I thought it would be cool to have a chapter on sorting anyway.  And because I had seen that that there was a need for somebody to write about sorting.  There were lots of of of uninformed articles out there about it that I'd seen in the literature.  So I started working on sorting in it.  And all of a sudden I'm able to use my math what I've learned in mathematics to learn about  sorting. And and and besides I'm in correspondence with Bob Floyd, who also has good ideas about  sorting and mathematics and combinations.  So that all of a sudden that then I had this aha moment where I where I where I I saw that  by studying a computer method quantitatively instead of qualitatively, I can not only see  that work, but I could say that it it worked 13 percent better than this other method.  And not just not not only that was better, but that it was that I could quantify exactly  how how fast the method was.  And and well, actually the aha moment had come in the summer of 62 when I was writing  a for-trade compiler.  I was in the midst of writing that compiler. One of the things a compiler has to do is is  the programmer makes up the name for quantity in his program.  And I and the computer has to figure out has to look up that name and see if that name has  occurred before.  And and and and the the method used in this inside the compiler is called hashing.  And so there was a technique that would work in the small computers we had in those days  that would work.  It would work especially well that that would that would be able to decide what you know  what identify somebody has a name, you know, al pha or something like this.  And the computer looks it up and says, oh, yeah, that that's something that that I know  this is a certain part of your program.  So there was there was a hashing method that they had worked, but nobody knew how well  it worked.  And and there was a rumor that some students at Princeton had worked had tried to solve  this problem unsuccessfully.  Yeah.  But but I took one one day off from writing the compiler because it was kind of tedious  working seven days a week, just turning out code.  So I spent a day saying, well, let me see if I can figure out how fast hashing goes.  And again, I got lucky and and I was able to solve the problem and use the different kind  of mathematics and I'd seen before.  And so I I wrote a few pages of notes on it.  And and then it occurred to me, you know, this could be a lifetime.  This could be a lifetime of of of using mathematics to say how good computer algorithms are.  So that was really that was really to me the most important change in direction in my life,  I would say is most of the evolution of your thought happening principally.  And this may not be a question worth answering conversations with yourself or conversation  with others.  Is it is it mostly a lonely or social inquiry that you're proceeding on in this case?  So it's a great question.  I I and they say I was mostly just going downhill in those days.  But but but I was but also my parents instilled in me this idea of service and teaching.  So I also look at it as not a struggle against people, but a struggle against ignorance and  to advance advance knowledge and to have something that that other people can use.  And and and so so here I have this that you know, I've analyzed this algorithm and I really  and I say, well, I, you know, there was a there was a young subject at the time called queuing  theory where people had taken a particular kind of algorithm of studying people who are  standing in line and figuring out the characteristics of what are what are good ways to service people  in line.  And that was the only existing algorithm, except a few sorting out that have been analyzed.  And so I and so I said, wait, no, here I took hashing and I was able to handle hashing.  I was able to analyze that.  And and so there must be there must be hundreds of other important algorithms that could be  analyzed.  And so this could be this could be something that would there would be, you know, really  of service to a lot of people if this gave in and to develop this kind of that's wonderful  to hear.  This is a process.  I'm going to ask them general things that of course also have complex answers.  But among your other achievements, we all know it, of course, is if you will, the your inquiry  into the elegance of type setting in this new form of communication.  What set you on that goal?  I mean, your achievement of a kind of lasting, both archival and elegant type setting is  something that you are much celebrated.  How did that come to be?  Okay, well, partly I married an artist who could who could introduce me to aesthetics  and we took some classes together.  And so I got to I got to understand more about that.  But you know, it's by Osmosis from my wife, let's say.  Yes.  Also, as I say, I loved my Edison Wesley textbooks when I was an undergraduate.  And they had the only publishing house that had their own their in-house composition and  design.  The other publishers were were outsourcing it.  And so I had I had developed some kind of, you know, just as a reader of books that appealed  to me, I had developed a little bit of sense that way.  And so when I was approached by us and Wesley to write books, I was thinking, OK, great,  I can have my books are going to look just as good too.  Then there was a revolution in the type setting world, which went away from metal type.  And and no, and and all the people who knew how to do it with the old equipment were dying  off and the new machines have not been adapted to mathematics or technical or technical work.  And so when I so I had revised my books for the for the second edition of volume two, the  proofs came back and made me made me sick because it was just extremely poor.  It was it was nowhere near looking like the books had looked before.  And and I mean, it was unbelievably bad that the the subscripts were in a different style  of type than the than the other parts of a formula and and letters were crooked and blotched.  And and really there was so little market for technical type setting that that all the all  the publishers had just gone for the their paying customers.  So so I was I was in despair until I I happened to see an example of a a book that had been  type set on a new kind of machine, which was entirely digital, entirely made of of  black and white dots, black dots on a page.  And this machine was able to produce books that were that looked like the best of metal type.  If if if one just wrote the computer program to decide where the blacks are going and where  the whites should go.  And and so once they saw that it only took a computer programming in order to solve my  problem, then I decided to spend a year figuring out how to write those programs.  You know, again, I underestimated and it took 10 years.  Something again to a layman who has talked with mathematicians and computer  scientists, you're both that it's important, particularly mathematics, to use words and  think in elegant terms.  The aesthetic phrases that are often used not so much by computer scientists, but certainly  seems to me that search for elegance seem to have informed not only your intellectual  background, but your visual background in in your contributions to computers.  Is that fair to say?  Well, the the aesthetic notion of beauty is inherent to to mathematics as well as and  I I one of the reasons I call my book the art of computer programming was because it has  some aesthetic art.  Exactly, it has some something about the beauty in it as well.  In your continued years, because we can't really explore them at Stanford, which is  of course, very important part of your life.  I think you wound up with a title which the art of computing is inherent in the title  there must be the only one in the world.  No, I don't think so.  No, well, if it exists, it's because you.  Well, but anyway, my touring lecture was actually about computer programming as an art, or it's  the title.  And I addressed the question there, what does the word art mean?  And what does it mean when you say something as an art and not a science?  There's all kinds of famous things like, you know, it's clever, but is it art and so on.  But the word really means is really more close to artisan and artificial.  Artisan, yes.  Artificial.  It means it means something that's not in nature, something that human beings have added  to the natural world.  But then, I mean, in German, the same word.  But then it often means then the fine arts and connects to this, these ideas of elegance  and beauty.  But really, it mostly means something that's not in the natural world.  I see.  So the beauty's incidental.  It's what we added on though.  Another very broad question I wanted to ask you, and you've had other people wonder at  this before, is how faith operates in your life which is compatible to that of a mathematician  and computer scientist.  And you've actually written about this.  Is it unusual in your field and profession to welcome faith as well as science?  Yeah, well, it's hard to say that people don't broadcast this very much.  But in the academic world, there are more people who broadcast their lack of faith, I  wouldn't say.  And so I had this great opportunity when people at MIT asked me if I would come in 1999 and  give a series of lectures that would talk about the relations between faith and science.  And this was the second or third year of a program that they had had.  But this year, they wanted, in the previous years, they had just had guest lectures about  a bunch of people.  But this time, I was supposed to do all six.  And so I figured, well, what better, if I was ever going to do something like this,  what better place to do it than Boston at MIT because they had also all these great theological  schools around there and Harvard and where I had spent some time.  So I couldn't resist the temptation.  Of course.  I wanted to.  It's an elegant invitation.  But yeah.  So then I gave these lectures.  And the lectures were hour and a half each and about 30 minutes of that I prepared and  an hour where I would just answer the questions of all the people in the audience that cover  the whole thing.  So this was transcribed into a book and people couldn't look at it.  But the way I overall, in general, I think, well, computer science is wonderful, mathematics  is wonderful, but it's not everything.  And as I said, I like the fact that with mathematics, I could get to different answers.  But I also am happy that there are things that are beyond my ken and questions that I'll  never know the answers to, but mysteries that I can learn more and more about.  I wouldn't be happy if everything was a mystery, but I'm also not happy if nothing is a mystery.  Maybe that's a way to think about it that in some ways in science, modern science, there's  an intolerance of mystery or a kind of irritation with mystery.  And hubris, once we've solved something, then we can solve everything.  And so I find the opposite.  When I learn something new, then I also learn more that I don't know.
The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_0_95.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_96_395.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_396_491.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_492_10523.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_10524_10619.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_10620_10679.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_10680_10883.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_10884_10967.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_10968_11423.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_11424_11531.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_11532_11807.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_11808_11855.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_11856_11939.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_11940_12131.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_12132_12179.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_12180_13967.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_13968_16055.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_16056_17399.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_17400_25295.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_25296_26615.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_26616_28583.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_28584_37319.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_37320_38351.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_38352_39407.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_39408_39455.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_39456_40187.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_40188_40439.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_40440_41771.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_41772_46763.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_46764_46823.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_46824_47087.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_47088_48095.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_48096_48875.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_48876_49139.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_49140_49535.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_49536_50351.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_50352_51947.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_51948_52487.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_52488_52739.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_52740_52907.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_52908_53123.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_53124_53555.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_53556_53639.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_53640_53783.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_53784_54251.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_54252_55511.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_55512_56159.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_56160_57179.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_57180_57443.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_57444_57791.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_57792_57875.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_57876_59723.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_59724_59891.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_59892_60191.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_60192_60371.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_60372_60431.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_60432_60563.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_60564_62075.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_62076_62543.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_62544_62879.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_62880_63815.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_63816_63971.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_63972_64223.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_64224_64367.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_64368_64451.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_64452_64499.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_64500_64547.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_64548_64667.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_64668_67307.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_67308_67475.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_67476_67559.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_67560_68423.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_68424_68591.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_68592_68783.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_68784_68891.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_68892_68975.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_68976_69059.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_69060_69335.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_69336_69443.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_69444_81671.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_81672_84815.png The_Heidelberg_Laureate_Forum_Foundation_presents_the_HLF_Portraits__Donald_Ervin_Knuth_BYkFfCqen7M_84816_85548.png