Forgot your password?
typodupeerror
Programming IT Technology

Knuth: All Questions Answered 400

Posted by timothy
from the art-of-computer dept.
sunhou writes: "The AMS published a lecture by Donald Knuth called All Questions Answered (pdf), where Knuth simply responded to questions from the audience. Topics ranged from errors in software ('I think Microsoft should say, "You'll get a check from Bill Gates every time you find an error"') to how he gets distracted by fonts on restaurant menus, to software patents. There were some really good questions (and responses)."
This discussion has been archived. No new comments can be posted.

Knuth: All Questions Answered

Comments Filter:
  • by Lunar82 (541435) <lunar82@gundampilot.org> on Saturday March 16, 2002 @10:46PM (#3175581)
    So I made up my own Knuth interview

    All Questions Answered
    Donald Knuth
    318 NOTICES OF THE AMS VOLUME 49, NUMBER 3
    On October 5, 2001, at the Technische Universität
    München, Donald Knuth presented a lecture entitled "All Questions Answered". The lecture drew an audience of around 350 people. This article contains the text of the lecture, edited by Notices senior writer and deputy editor Allyn Jackson.
    Originally trained as a mathematician, Donald
    Knuth is renowned for his research in computer science, especially the analysis of algorithms. He is a prolific author, with 160 entries in MathSciNet. Among his many books is the three-volume series The Art of Computer Programming [TAOCP], for which he received the AMS Steele Prize for Exposition in 1986. The citation for the prize stated that TAOCP "has made as great a contribution to the teaching of mathematics for the present generation of students as any book in mathematics proper in recent decades." The long awaited fourth volume is in preparation and some parts are available through Knuth's website, http://www-cs-faculty. stanford.edu/~knuth/.
    Knuth is the creator of the TEX and METAFONT
    languages for computer typesetting, which have
    revolutionized the preparation and distribution of
    technical documents in many fields, including mathematics.
    In 1978 he presented the AMS Gibbs Lecture
    entitled "Mathematical Typography". The lecture
    was subsequently published in the Bulletin of the
    AMS [MT].
    Knuth earned his Ph.D. in mathematics in 1963
    from the California Institute of Technology under
    the direction of Marshall Hall. He has received the
    Turing Award from the Association for Computing
    Machinery (1974), the National Medal of Science
    (1979), the Adelsköld Medal from the Royal Swedish
    Academy of Sciences (1994), the Harvey Prize from
    the Technion of Israel (1995), the John von Neumann
    Medal from the Institute of Electrical and Electronics
    Engineers (1995), and the Kyoto Prize from the
    Inamori Foundation (1996). Since 1968 Knuth has
    been on the faculty of Stanford University, where
    he currently holds the title of Professor Emeritus of
    The Art of Computer Programming.
    --Allyn Jackson
    Knuth: In every class that I taught at Stanford,
    the last day was devoted to "all questions answered".
    The students didn't have to come to class
    if they didn't want to, but if they did, they could
    ask any question on any subject except religion or
    politics or the final exam. I got the idea from
    Richard Feynman, who did the same thing in his
    classes at Caltech, and it was always interesting to
    see what the students really wanted to know. Today
    I'll answer any question on any subject. Do we
    allow religion or politics? I don't know. But there
    is no final exam to worry about. I'll try to answer
    without taking too much time so that we can get a
    lot of questions in.
    So, who wants to ask the first question?... Well,
    if there are no questions...[Knuth makes as if to
    leave.]
    Question: There was a special report to the American
    president, the PITAC report [PITAC], containing
    some recommendations. I am wondering
    whether you would be willing to comment on the priorities
    outlined in these recommendations:
    better software engineering, building a teraflop
    MARCH 2002 NOTICES OF THE AMS 319
    computer, improvements in the Internet including
    higher security and higher bandwidth, and the
    socio-economic impacts of managing information
    available via computer networks.
    Knuth: I think that's a brilliant solution of the
    problem of what to present to a president. But in
    fact what I would like to see is thousands of computer
    scientists let loose to do whatever they want.
    That's what really advances the field. From my experience
    writing The Art of Computer Programming,
    if you asked me any year what was the most important
    thing that happened
    in computer science that year,
    I probably would have no answer
    for the question, but over
    five years' time the whole field
    changes. Computer science is
    a tremendous collaboration
    of people from all over the
    world adding little bricks to a
    massive wall. The individual
    bricks are what make it work,
    and not the milestones.
    Next question?
    Question: Mathematicians
    say that God has the "Book of
    Proofs", where all the most
    aesthetic proofs are written.
    Can you recommend some
    algorithms for the "Book of Algorithms"?
    Knuth: That's a nice question.
    It was Paul Erdos who
    promulgated the idea that God has a book containing
    the best mathematical proofs, and I guess
    my friend Günter Ziegler in Berlin has recently
    written about it [PFB].
    I remember that mathematicians were telling
    me in the 1960s that they would recognize computer
    science as a mature discipline when it had
    1,000 deep algorithms. I think we've probably
    reached 500. There are certainly lots of algorithms
    that I think have to be considered absolutely beautiful
    and immortal, in some sense. Two examples
    are the Euclid algorithm and a corresponding one
    that works in binary notation and that may have
    been developed independently in China, almost as
    early as Euclid's algorithm was invented in Greece.
    In my books I am mostly concerned with the algorithms
    that are classical and that have been around
    for a long time. But still, every year we find brand
    new ideas that I think are going to remain forever.
    Question: Do you have thoughts on quantum
    computing?
    Knuth: Yes, but I don't know a great deal about
    it. It's quite a different paradigm from what I'm used
    to. It has lots of things in common with the kind
    of computing I know, but it's also quite mysterious
    in that you have to get all the answers at the end;
    you don't make a test and then have that determine
    what you do next. A lot of you have seen the movie
    Lola rennt (called Run Lola Run in the U.S.), in which
    the plot is played out three different times, with the
    outcome taking three different branches. Quantum
    computing is something like that: The world goes
    into many different branches, and we're interested
    in the one where the outcome is the nicest.
    I'm good at nonquantum computing myself, so
    it's quite possible that if quantum computing takes
    over, I won't be able to do the new stuff. My life's
    work is with computers not
    because I'm interested so
    much in computation, but because
    I happen to be good at
    this kind of computing. Fortunately
    for me, I found that
    the thing I could do well was
    interesting to other people. I
    didn't develop an ability to
    think about algorithms because
    I wanted to help people
    solve problems. Somehow, by
    the time I was a teenager, I
    had a peculiar way of thinking
    that made me good at programming.
    But I might not be
    good at quantum programming.
    It seems to be a different
    world from my own.
    I'll take a question from
    the back.
    Question: I am working in
    theorem proving, and one of the most important papers
    is your paper "Simple word problems in universal
    algebra" [KB] from 1970, written with
    P. B. Bendix. I have two questions. The first is, do you
    still follow this area and what do you think of it? And
    the second is, who is and what became of P. B. Bendix?
    Knuth: This work was published in 1970, but I
    actually did it in 1967 while I was at Caltech. It
    was a simple idea, but fortunately it's turned out
    to be very widely applicable. The idea is to take a
    set of mathematical axioms and find all the
    implications of those axioms. If I have a certain
    set of axioms and you have a possible theorem,
    you ask, does this theorem follow from those
    axioms or not? I called my paper "Simple word
    problems in universal algebra", and I said a
    problem was "simple" if my method could
    handle it. Now people have extended the method
    quite a lot, so that a lot more problems are
    "simple". I think their work is beautiful.
    The year 1967 was the most dramatic year of
    my life by far. I had no time for research. I had
    two children less than two years old; I had been
    scheduled to be a lecturer for ACM (Association
    for Computing Machinery) for three weeks; I had
    NON SEQUITUR © 2001 Wiley Miller. Dist. By UNIVERSAL PRESS SYNDICATE.
    Reprinted with permission. All rights reserved.
    320 NOTICES OF THE AMS VOLUME 49, NUMBER 3
    to give lectures in a
    NATO summer school
    in Copenhagen; I had to
    speak in a conference at
    Oxford; and so on. And
    I was getting the page
    proofs for The Art of
    Computer Programming,
    of which the first
    volume was being
    published in 1968. All
    of this was in addition
    to the classes I was
    teaching, and an attack
    of ulcers that put me in
    the hospital, and being
    an editor for twelve
    journals. That year I
    thought of two little
    ideas. One has become
    known as the Knuth-Bendix algorithm; the other
    one is known as attribute grammars [AG]. That
    was the most creative year of my life, and it was
    also the most hectic.
    You asked about Peter Bendix. He was a sophomore
    in a class I taught at Caltech, "Introduction
    to Algebra". Every student was supposed to do a
    class project, and Peter did his term paper on the
    implementation of the algorithm. He was a physics
    major. This was the time of the Vietnam War, and
    he became an objector. He went to Canada and
    worked as a high school teacher for about five
    years and later got a degree in physics. I found he
    was living near Stanford a couple of years ago, so
    I called him up and found out that he has had a
    fairly happy life in recent years.
    In the 1960s, if I wrote a joint paper with my advisor
    Marshall Hall, it meant that he did the theory
    and I did the programming. But if I wrote a paper
    with anybody else, it meant that I did the theory and
    the other person did the programming. So Pete
    Bendix was a good programmer who implemented
    the method.
    Question: It seems to me it's easier to revise a
    book than the huge software programs we see day
    to day. How can we apply theory to improve software?
    Knuth: Certainly errors in software are more difficult
    to fix than errors in books. In fact, my main
    conclusion after spending ten years of my life working
    on the TEX project is that software is hard. It's
    harder than anything else I've ever had to do. While
    I was working on the TEX program, I was unable to
    do full-time teaching. Although I love teaching, I
    had to take a year off from it because there was just
    too much to keep in my head at one time. Writing a
    book is a little more difficult than writing a technical
    paper, but writing software is a lot more difficult
    than writing a book.
    In my books I offer rewards for the first person
    who finds any particular error, and I must say that
    I've written more checks to people in Germany
    than in any other country in the world. I get letters
    from all over, but my German readers are the best
    nitpickers that I've ever had! In software I similarly
    pay for errors in the TEX and METAFONT programs.
    The reward was doubling every year: It started out
    at $2.56, then it went to $5.12, and so on, until it
    reached $327.68, at which time I stopped doubling.
    There has been no error reported in TEX since
    1994 or 1995, although there is a rumor that somebody
    has recently found one. I'm going to have to
    look at it again in a year or two. I do everything in
    batch mode, by the way. I am going to look again
    at possible errors in TEX in, say, the year 2003.
    I think letting users know that you welcome reports
    of errors is one important technique that
    could be used in the software industry. I think
    Microsoft should say, "You'll get a check from Bill
    Gates every time you find an error."
    Question: What importance do you give to the design
    of efficient algorithms, and what emphasis do
    you suggest giving this area in the future?
    Knuth: I think the design of efficient algorithms
    is somehow the core of computer science. It's at
    the center of our field. Computers are incredibly
    fast now compared to what they were before, so
    for many problems there is no need to have an efficient
    algorithm. I can write programs that are in
    some sense extremely inefficient, but if it's only
    going to take one second to get the answer, who
    cares? Still, some things we have to do millions or
    billions of times, and just knowing that the number
    of times is finite doesn't tell us that we can handle
    it. So the number of problems that are in need
    of efficient algorithms is huge. For example, many
    problems are NP complete, and NP complete is
    just a small level of complexity. Therefore I see an
    almost infinite horizon for the need for efficient
    algorithms. And that makes me happy because
    those are the kinds of problems I like the best.
    MARCH 2002 NOTICES OF THE AMS 321
    Question: You have a big interest in puzzles, including
    the "Tower of Hanoi" puzzle on more than
    3 pegs. I won't ask a harder question--what is the
    shortest solution?--because I am not sure everyone
    knows this puzzle. But I will ask a more philosophical
    question: Is it possible to show this can never be
    solved?
    Knuth: Do people know the "Tower of Hanoi"
    problem? You have 3 pegs, and you have disks of
    different sizes. You're supposed to transfer the disks
    from one peg to another, and the disks have to be
    sorted on each peg so that the biggest is always on
    the bottom. You can move only one disk at a time.
    Henry Dudeney invented the idea of generalizing
    this puzzle to more than 3 pegs, and the task of finding
    the shortest solution to the 4-peg problem has
    been an open question for more than a hundred
    years. The 3-peg problem is very simple; we teach it
    to freshmen.
    But take another, more famous problem, the
    Goldbach conjecture in mathematics: Every even integer
    is the sum of two odd primes. Now, I think
    that's a problem that's never going to be solved. I
    think it might not even have a proof. It might be
    one of the unprovable theorems that Gödel showed
    exist. In fact, we now know that in some sense almost
    all correct statements about mathematics are
    unprovable. Goldbach's conjecture is just, sort of,
    true because it can't be false. There are so many
    ways to represent an even number as the sum of
    two odd numbers, that as the numbers grow the
    number of representations grows bigger and bigger.
    Take a 101010-digit even number, and imagine
    how many ways there are to write that as the sum
    of two odd integers. For an n-bit odd number, the
    chances are proportional to 1/n that it's prime. How
    are all of those pairs of odd numbers going to be
    nonprime? It just can't happen. But it doesn't follow
    that you'll find a proof, because the definition
    of primality is multiplicative, while Goldbach's conjecture
    pertains to an additive property. So it might
    very well be that the conjecture happens to be
    true, but there is no rigorous way to prove it.
    In the case of the 4-peg "Tower of Hanoi", there
    are many, many ways to achieve what we think is
    the minimum number of moves, but we have no
    good way to characterize all those solutions. So
    that's why I personally came to the conclusion that
    I was never going to be able to solve it, and I
    stopped working on it in 1972. But I spent a solid
    week working on it pretty hard.
    Question: What are the five most important problems
    in computer science?
    Knuth: I don't like this "top ten" business. It's
    the bottom ten that I like. I think you've got to
    go for the little things, the stones that make up
    the wall.
    Question: You
    spent a lot of time on
    computer typesetting.
    What are your reflections
    on the impact of
    this work?
    Knuth: I am extremely
    happy that
    my work was in the
    public domain and
    made it possible for
    people on all platforms
    to communicate
    with each other
    via the Internet. Especially
    now I'm thrilled
    by some recent projects.
    Two weeks ago
    I heard a great lecture
    by Bernd Wegner from
    the Technical University
    of Berlin about
    the plans for online
    journals by the European
    Mathematical Society.
    Such things
    would simply have
    been impossible without
    the open source
    software that came
    out of my work. So I'm
    extremely delighted
    this is helping to advance
    science.
    I'm happy to see
    many books that look
    pretty good. Before I
    started my work,
    books on mathematics
    were looking worse
    and worse from year
    to year. It took a lot
    of skilled handwork
    to do it in the old system.
    The people who
    could do that were
    dying out, and high
    priority did not go to
    mathematical books.
    I never expected that
    TEX would take over the entire world of publishing.
    I'm not a very competitive person, and I did not
    want to take jobs away from anybody who was
    doing another way of printing. But I found that nobody
    wanted to do mathematical publishing well,
    so math was something I could improve without
    getting anybody upset about me being an upstart.
    The downside is that I'm too sensitive to things
    now. I can't go to a restaurant and order food
    322 NOTICES OF THE AMS VOLUME 49, NUMBER 3
    because I keep looking at the fonts on the menu.
    Five minutes later I realize that it's also talking
    about food. If I had never thought about computer
    typesetting, I might have had a happier life in some
    ways.
    Question: Can you give us an outline for computer
    science, some milestones for the next ten or
    twenty years?
    Knuth: You're asking for milestones again.
    There is a lot of interest in applications to biology
    because so many things have opened up in that
    domain, with chances to cure diseases. The fact
    that human beings are based on a discrete code
    means that people like you and me, who are good
    at discrete problems, are able to do relevant work
    for this area. The problems are very difficult and
    challenging, and that's why I foresee an important
    future there.
    But in all aspects of our field, I really don't see
    any slowing down. Every time I think I've discovered
    something interesting, I look on the Internet
    and find that somebody else has done it too. So we
    have a field that at the moment still seems to be
    like a boiling kettle, where you can't keep the lid
    on.
    In the field of biology, I think we can confidently
    predict that it's going to have rich problems to
    solve for at least 500 years. I can't make that claim
    for computer science.
    Question: What is the connection between mathematics
    and computer programming viewed as an
    art?
    Knuth: Art is Kunst. The American movie
    Artificial Intelligence is called Kunstlicher Intelligenz
    in Germany--that is, artificial as well as artistic. I
    think of programming with beauty in mind, as
    being something elegant, something that you can
    be proud of for the way it fits together. Mathematics
    in the same way has elegance. Both fields, computing
    and mathematics, are different from
    other sciences because they are artificial; they
    are not in nature. They're totally under our own
    control. We make up the axioms, and when we
    solve a problem, we can prove that we've solved it.
    No astronomer will ever know whether his theories
    of astronomy are correct. You can't go up to the sun
    and measure it.
    So these are my first thoughts on that connection.
    But there is a difference between mathematics
    and computer programming, and sometimes I
    can feel when I'm putting on one hat or the other.
    Some parts of me like mathematics, and some
    parts of me like emacs hacking. I think they go
    together okay, but I don't see that they're the same
    paradigm.
    Question: What is the relationship between God
    and computers?
    Knuth: In one of my books, 3:16 Bible Texts
    Illuminated [BTI], I used random sampling to study
    sixty different verses of the Bible and what people
    from all different religious persuasions and different
    centuries have said about those verses. I did
    the study at first on my own, and then I found it
    was interesting enough that I ought to make a book
    about it. I got sixty of the best artists in the world
    to illustrate the book, many of them in Germany.
    The artwork was exhibited twice in Germany, and
    in other countries around the world. It was also
    shown in the National Cathedral in Washington,
    DC. In that book I used methodology that computer
    scientists often use for understanding a
    complicated subject, to see if that method would
    give some insight into the Bible, which is a complicated
    subject. In the book, I don't give answers.
    I just say I think it's good that life should be an
    ongoing search. The journey is more important
    than the destination.
    Question: Do you know whether "P equals NP"
    has been proved? I heard a rumor that it has.
    Knuth: Which rumor did you hear?
    Question: One from Russia.
    Knuth: From Russia? That's new to me. Well, I
    don't think anybody has proved that P equals NP
    yet. But I know that Andy Yao has retired and
    hopes to solve the problem in the next five to
    ten years. He is inspired by Andrew Wiles, who
    MARCH 2002 NOTICES OF THE AMS 323
    devoted several years to proving Fermat's Last
    Theorem. They're both Princeton people. Andy
    can do it if anybody can.
    Three or four years ago, there was a paper in a
    Chinese journal of computer science and technology
    by a professor who claimed he could solve an
    NP-hard problem in polynomial time. The problem
    was about cliques, and he had a very clever way to
    represent cliques. The method was supposedly
    polynomial time, but it actually took something like
    n12 steps, so you couldn't even check it when n
    equals 5. So it was very hard to see the bug in his
    proof. I went to Stanford and sat down with our
    graduate students, and we needed a couple of
    hours before we found the flaw. I wrote the author
    a letter pointing out the error, and he wrote back
    a couple of months later, saying, "No, no, there is
    no error." I decided not to pursue it any further. I
    had done my part. But I don't believe it's been
    solved. That's the most mind-boggling problem
    facing theoretical computer science, and maybe
    all of science at the moment.
    Question: What do you think of research in
    cryptographic algorithms? And what do you
    think of efforts by politicians today to put limits on
    cryptography research?
    Knuth: Certainly the whole area of cryptographic
    algorithms has been one of the most active and exciting
    areas in computer science for the past ten
    years, and many of the results are spectacular and
    beautiful. I can't claim that I'm good at that particular
    subject, though, because I can't think of
    sneaky attacks myself. But the key problem is,
    what about the abuse of secure methods of communication?
    I don't want criminals to use these
    methods to become better criminals.
    I'm a religious person, and I think that God
    knows all my secrets, so I always feel that whatever
    I'm thinking is public knowledge in some way. I
    come from this kind of background. I don't feel
    I have to encrypt everything I do. On the other
    hand, I would certainly feel quite differently if
    somebody started to use such openness against me,
    by stealing my bank accounts or whatever. So I am
    supportive of a high level of secrecy. But whether
    it should be impossible for the authorities to
    decode things even in criminal investigations, in
    extreme cases--there I tend to come down on the
    side of wanting to have some way to break some
    keys sometimes.
    Question: Will we have intelligent machines sometime
    in the future? Should we have them?
    Knuth: There have always been inflated estimates
    as to how soon we are going to have a
    machine that's intelligent. I still see no signs of
    getting around the central problem of understanding
    what is cognition, what it means to think.
    Neurologists are making better measurements
    than they ever have before, but we are still so far
    from finding an answer that I can't yet rank
    neuroscience as one of the most active fields of
    current work. Biology has been getting answers,
    with DNA and stem cells and so on. But with cognition
    we are still looking for the secret.
    Some very thought-provoking books came out
    a year or two ago, one by Hans Moravec [Mo], and
    one by Ray Kurzweil [Ku]. Both of them are saying
    that in twenty or thirty years we are going to have
    machines smarter than humans. Some people were
    worried about that. My attitude is, if that's true,
    more power to them. If they are smarter than us,
    so what? Then we can learn from them. But I see
    no signs that there are any breakthroughs around
    the corner.
    Two weeks ago in Greece I was at the inauguration
    of a new book by Christos Papadimitriou, who
    is chairman of computer science at Berkeley. He
    published a novel in the Greek language called The
    Smile of Turing [Pa]. I don't want to give away the
    story, but when it gets published in German or
    English, you'll find that it has a very nice discussion
    of artificial intelligence and the Turing test for
    intelligence.
    The most promising model of how the brain
    works that I've seen says that the brain is a dynamic
    genetic algorithm that operates all the time. As I
    324 NOTICES OF THE AMS VOLUME 49, NUMBER 3
    am talking to you now, your brains have a lot of
    competing theories about what I'm going to say. It's
    the survival of the fittest, a continual
    battle among the competing theories.
    Some come to the surface and actually
    enter your consciousness, but the
    others are all there. Some kind of mating
    of concepts might be going on in our
    heads all the time. This model seems to
    have the right properties to account for
    how we can do what we do with the
    relatively slow response time that our
    neurons have. But I am by no means an
    expert on this.
    Question: What is your thinking about
    software patents? There is a big discussion
    going on in Europe right now about
    whether software should be patentable.
    Knuth: I'm against patents on things
    that any student should be expected to
    discover. There have been an awful lot
    of software patents in the U.S. for ideas
    that are completely trivial, and that
    bothers me a lot. There is an organization
    that has worked for many years to
    make patents on all the remaining trivial
    ideas and then make these available
    to everyone. The way patenting had
    been going was threatening to make
    the software industry stand still.
    Algorithms are inherently mathematical
    things that should be as unpatentable
    as the value of . But for
    something nontrivial, something like
    the interior point method for linear programming,
    there's more justification
    for somebody getting a right to license
    the method for a short time, instead of
    keeping it a trade secret. That's the
    whole idea of patents; the word patent
    means "to make public".
    I was trained in the culture of mathematics, so
    I'm not used to charging people a penny every time
    they use a theorem I proved. But I charge somebody
    for the time I spend telling them which theorem
    to apply. It's okay to charge for services and
    customization and improvement, but don't make
    the algorithms themselves proprietary.
    There's an interesting issue, though. Could you
    possibly have a patent on a positive integer? It is
    not inconceivable that if we took a million of the
    greatest supercomputers today and set them going,
    they could compute a certain 300-digit constant
    that would solve any NP-hard problem by taking
    the GCD of this constant with an input number, or
    by some other funny combination. This integer
    would require massive amounts of computation
    time to find, and if you knew that integer, then you
    could do all kinds of useful things. Now, is that
    integer really discovered by man? Or is it something
    that is God given? When we start thinking of complexity
    issues, we have to change our viewpoint as
    to what is in nature and what is invented.
    Question: You have been writing checks to people
    who point out errors in your books. I have never
    heard of anyone cashing these checks. Do you know
    how much money you would be out of, if everyone
    suddenly cashed the checks?
    Knuth: There's one man who lives near Frankfurt
    who would probably have more than $1,000
    if he cashed all the checks I've sent him. There's a
    man in Los Gatos, California, whom I've never met,
    who cashes a check for $2.56 about once a month,
    and that's been going on for some years now.
    Altogether I've written more than 2,000 checks
    over the years, and the average amount exceeds
    $8.00 per check. Even if everybody cashed their
    checks, it would still be more than worth it to me
    to know that my books are getting better.
    References
    [TAOCP] The Art of Computer Programming, by Donald E.
    Knuth. Volume 1: Fundamental Algorithms (third
    edition, Addison-Wesley, 1997). Volume 2: Seminumerical
    Algorithms (third edition, Addison-Wesley,
    1997). Volume 3: Sorting and Searching (second
    edition, Addison-Wesley, 1998). Volume 4: Combinatorial
    Algorithms (in preparation).
    [MT] Mathematical typography, by Donald E. Knuth. Bull.
    Amer. Math. Soc. (N.S.) 1 (1979), no. 2, 337-372.
    Reprinted in Digital Typography (Stanford, California:
    CSLI Publications, 1998), pp. 19-65.
    [PITAC] President's information technology advisory committee.
    See http://www.itrd.gov/ac/.
    [PFB] Proofs from The Book, by Martin Aigner and Günter
    Ziegler. Second edition, Springer Verlag, 2001.
    [KB] Simple word problems in universal algebras, by
    Peter B. Bendix and Donald Knuth. Computational
    Problems in Abstract Algebra, J. Leech, ed. (Oxford:
    Pergamon, 1970), pp. 263-297. Reprinted in Automation
    of Reasoning, Jörg H. Siekmann and Graham
    Wrightson, eds. (Springer, 1983), pp. 342-376.
    [BTI] 3:16 Bible Texts Illuminated, by Donald E. Knuth.
    A-R Editions, Madison, Wisconsin, 1990.
    [AG] Semantics of context-free languages, by Donald E.
    Knuth. Mathematical Systems Theory 2 (1968),
    127-145. See also The genesis of attribute grammars,
    in Lecture Notes in Computer Science 461
    (1990), 1-12.
    [Pa] TO XAMOGELO TOY TOYRINGK (The Smile of Turing),
    by Christos Papadimitriou. Livani Publishers,
    Athens, Greece, 2001.
    [Ku] The Age of Spiritual Machines: When Computers Exceed
    Human Intelligence, by Ray Kurzweil. Penguin
    USA, 2000.
    [Mo] Robot: Mere Machine to Transcendent Mind, by
    Hans P. Moravec. Oxford University Press, 2000.
    Photographs used in this article are courtesy of
    Andreas Jung, Technische Universität München.
  • Mirror (Score:4, Informative)

    by Russ Nelson (33911) <slashdot@russnelson.com> on Saturday March 16, 2002 @11:01PM (#3175628) Homepage
  • Mirror here (Score:2, Informative)

    by Anonymous Coward on Saturday March 16, 2002 @11:05PM (#3175641)
    Computer Literacy Interview With Donald Knuth
    By Dan Doernberg
    December 7th, 1993


    CLB: You have just-published books on both CWEB and the Stanford GraphBase, two areas of your own research. Let's start with CWEB, which integrates C and TeX to facilitate program documentation.

    Knuth: The CWEB system is an add-on to C that makes programming better than any other method known in the world, by far. I simply have to be honest and say that it's the greatest thing that's there. The CWEB System of Structured Documentation is the definitive user manual and complete explanation, more than anybody really needs to know about CWEB.

    CLB: You've said that CWEB gives an order of magnitude improvement in programmer productivity--- how so?

    Knuth: Well, maybe not an order of magnitude, maybe only a factor of two. People who have used CWEB have noticed that they write better programs, that the programs are more portable, more easily debugged, more easily maintained... and they don't take as long to write.

    CLB: Has CWEB been used just at Stanford, or in industry as well?

    Knuth: It's being used around the world. We've had WEB, the original version (for Pascal) in a variety of systems, and then more and more people started getting infected by it. TeX was written in WEB. Silvio Levy did the conversion to CWEB in 1987. It was experimental for a long time, and now I'm just saying "The experiment worked!". CWEB is much better than WEB, because C is a much nicer language to work with for system programming and lots of other things. For anybody who really cares about programming, I have no idea why they would not prefer this to any other system.

    CLB: Easy to use, runs fast, all that good stuff?

    Knuth: Right, and it makes you happy after you finish writing a program!

    CLB: Even if you write a bad program?!

    Knuth:(Don's wife--Ed.) Almost... well... yeah! Jill will tell you, I come out of my office several times a week saying, "CWEB programming is such fun!" It's true, I just can't do enough of it.

    The frame of mind that you're in when you're writing a CWEB program is that much better than the old attitude. You think of yourself as writing for a human being, explaining to a human being what a computer should do, instead of thinking of yourself as talking to the computer telling it what to do. You get your act together better when you're explaining it to another person. This approach helps even for a program that you're going to throw away after an hour. CWEB is a tool that I recommend using even if you're writing a program only for yourself, for your eyes only.

    CLB: CWEB seems very close to the structured programming models of the 70s...

    Knuth: Right, it's the next step. With structured programming, there were some people saying program top-down, and others saying program bottom-up. With WEB/CWEB you can do parts of it bottom-up and parts of it top-down, whatever you feel is right for the program, or for the part of the program you're in.

    The structured programming methodology was great... but the way to really understand it is not as a cookbook of rules, but as a way to understand the relation between high-level and low-level views of a program. The way you do that is by viewing the program as a web, as a bunch of small pieces that are simple in themselves and that have simple connections to other small pieces. This way of understanding the complex whole in terms of simple small parts, and the connections between those parts, is supported by the WEB scheme.

    You can create the parts in whatever order is psychologically best for you. Sometimes you can create them from the bottom up. Bottom-up means that you know somehow that you probably need a subroutine that will do something, so you write it now while you're ready, while you're psyched for it. With this bottom- up programming, your pencil gets more powerful every page, because on page nine you've developed more tools that you can use on page ten... your pencil is stronger.

    With top-down programming you start at the beginning and say "I'm going to do this first and then this, and then this"... but then you have to spell out what those are--- you can wind up gasping for breath a hundred pages later when you finally figure out how you're actually going to do those things!

    Top-down programming tends to look very nice for the first few pages and then it becomes a little hard to keep the threads going. Bottom-up programming also tends to look nice for a while, your pencil is more powerful, but that means you can also do more tricky stuff. If you mix the two in a good psychological way, then it works, even at the end.

    (TeX: The Program--Ed.) I did this with TeX, a very large program: 500+ pages of code in the book . Throughout that entire program, all those lines of code, there was always one thing that had to be the next thing I did. I didn't really have much choice; each step was based on what I'd done so far. No methodology would teach me how to write a piece of software like that, if I followed it rigorously. But if I imagined myself explaining the program to a good competent programmer, all that this long program was, then there was just this one natural way to do it. The order in which the code appears in the book is the order in which I wrote it.

    CLB: To what extent did you or do you follow the "holy war" debates about software engineering methodologies?

    Knuth: I didn't follow every nuance of that work, but I was aware of the dominant ideas. I didn't know what the CASE tools were until many years after other people did. I think it was bad to make too much of a religion out of it. There was a lot of "political correctness" about how to program in those days.

    There was a similar thing in the mathematics community in the 1920's, where people were saying that good mathematicians would have to prove theorems a certain way. You weren't supposed to use certain tools of proof that some people thought might lead you into paradoxes. It was like trying to do mathematics with a hand tied behind your back. Similarly, politically correct structured programming was keeping people from getting good programs done, when they knew perfectly well what they were doing, just because their approach didn't happen to fit with the current idea of correctness. Computer science is like every other field; it goes in waves of fashion. Some of the trends are good, but almost every good idea seems to get used in a different way than it should have been.

    For example, take random number generators. People had no theory about how to generate random numbers for fifteen years. Then somebody proved one small result about a particular method: if you averaged the serial correlation over an entire period of a billion numbers, the average would be zero, which was good. All of a sudden, everybody switched over, they took out all their old routines and converted to this new method, because it was the only one that had any theory to it whatsoever. It turned out this was a horrible random number generator; the theory had not noticed that the average over the first half was +1 and over the second half was -1! All through history, people have taken ideas and misunderstood the limitations of them.

    CLB: Which method was this?

    Knuth: Well, it was called RANDU in most subroutine libraries. It's been pretty well purged by now; still, if anybody sees a subroutine named RANDU, get rid of it!

    CLB: Did you integrate WEB with C because so many programmers today are using it, or do you personally like C and write with it?

    Knuth: I think C has a lot of features that are very important. The way C handles pointers, for example, was a brilliant innovation; it solved a lot of problems that we had before in data structuring and made the programs look good afterwards. C isn't the perfect language, no language is, but I think it has a lot of virtues, and you can avoid the parts you don't like. I do like C as a language, especially because it blends in with the operating system (if you're using UNIX, for example).

    All through my life, I've always used the programming language that blended best with the debugging system and operating system that I'm using. If I had a better debugger for language X, and if X went well with the operating system, I would be using that.

    An extreme case occurred one year I worked in a lab where the operating system had been designed by Ned Irons. The system was for one of Cray's early machines, and Irons had also written a compiler language called IMP. IMP had a lot of horrible features. One, it was an extensible language, and everybody in the lab would keep extending it. A program that worked on Monday wouldn't work on Tuesday, and the first thing that you'd do if your program failed was to check whether the compiled code was OK. The second thing about IMP was that it was an extremely terse language. For example, where in PASCAL you would say "IF X > 0 THEN...", in IMP you say "X+=>". In other words, your program was very short. You felt like you were writing elegant programs, because there were only a few characters, but you couldn't read them the next day! Being very terse meant that you couldn't fathom this bunch of marks on the page...

    CLB: I realize your current emphasis is on "literate programming", but were you ever whatsoever attracted to APL as a math-oriented language?

    Knuth: That's another story. APL is for people who have problems to solve and don't care too much about efficiency; they want a nice elegant way to state the solution to their problem, but the solution that they come up with is not necessarily anything that a computer has an easy job doing. It's a problem specification language, but not a system programming language... there is an APL-WEB.

    But I want to say more about IMP. The third thing against it was, if you made a mistake, the compiler would either get into an infinite loop, or it would stop on your first error and say "ERROR ERROR ERROR" and quit; you would have to figure out what the mistake was! It was not a great language or compiler.

    However... it was still my language of choice, because it fit that operating system perfectly. The arrays would be named in a way that you could easily see in the debugger, and you could know where the storage was being allocated, you knew what was going on, and you could actually get your program running reliably, because IMP blended with the operating system. You couldn't do that with any of the other languages. You might be writing with a better language, but you would get your work done a couple of weeks later, instead of getting answers. I used IMP.

    CLB: Was IMP being used at Stanford?

    Knuth: It was at a research lab in Princeton. A year before I came to Stanford, I worked there on a classified cryptanalysis research project.

    CLB: Please tell us about your other new book, The Stanford GraphBase.

    Knuth: The GraphBase book is for two kinds of people. It has a research purpose; the people who are working on the study of new algorithms for combinatorial problems need a standard set of test data on which to compete with each other, and for benchmarks. As I was preparing Volume IV of The Art of Computer Programming, I decided that I would make all the examples and data that I'm using in that book available to everyone. There was a need for some standard benchmarks, and everything should be well arranged so that it is easy to use in thousands of ways. So... I now have a collection of thousands of standard data sets; anyone in Poland can have exactly the same data as anyone in California or China. It's very portable, and can be downloaded from the Internet.

    The second purpose of the GraphBase hook is that it is an example of CWEB programming--- it's actually 32 examples of CWEB programming. They're short programs that illustrate the programming style that I prefer. The examples are like little essays, little short stories of computer programs, that are perhaps fun to read.

    CLB: What is your current hardware and software environment?

    Knuth: I use CWEB for my programming. I use the Emacs editor very heavily, and I use a great high-level language called METAPOST for drawing technical illustrations. This is a new language by John Hobby that is going to be released soon, I think. It's based on METAFONT. 75% of the code is mine from METAFONT, but it's fixed up so that it generates PostScript. I love it.

    I also use Mathematica. The people at Maple are trying to convince me to switch over to Maple, another excellent system. At the moment, I like Mathematica because you don't have to type your multiplication signs; you can say "2X" instead of "2*X". Also, the Mathematica manual is exceptionally good.

    CLB: You like Wolfram's writing style?

    Knuth: Especially the index... you can easily find your way around that book. With the first edition, when I had a new problem to solve, I would look in the index and it would almost always refer me to the right page. There were three or four times when the word I tried wasn't there, and I penciled in where to look when I had this problem next time. In the second edition those had all been fixed, and I had not reported them to anybody.

    CLB: Let me get your quick impressions on a few research areas, and whether you've read or done any work in them. The first is genetic algorithms. How do you feel about the general concept, that instead of the human determining the algorithm, you somewhat let the machine have at it...

    Knuth: I plan to do a lot of experimenting on this as I get into Volume IV. There's genetic breeding, there's simulated annealing, there are other strategies that people have developed. I have a method in The Stanford GraphBase book that I call "stratified greed". These techniques are all competing for the same kind of problems, and I want to try a lot of examples; some of them might work better on one than the other, and I want to get a feel for this. Certain problems are naturals for neural nets... genetic algorithms are likely to do well on tasks related to language recognition, and people say also like predicting the stock market or something like that. Somehow the closer a problem is to nature, the more you expect the genetic algorithm to work, while the closer it is to number theory or something artificial, the more you expect some other kind of approach will help. It's hard to understand the way these methods scale up; on a small problem they might do terrifically, and then they might break down completely just when the problem gets a little bit bigger... or it might go the other way.

    CLB: It sounds like you have several years of disciplined testing with your data sets ahead of you.

    Knuth: The Stanford GraphBase gives me an unlimited supply of problems that I and other people can do. I read what other people have claimed about their methods, but I also try them all myself. The original work I do in The Art of Computer Programming is to take the methods of two different authors and analyze method A from the standpoint of author B, and method B from the standpoint of author A. They have only given their sides of it, so I try to fill in ....

    CLB: What about object-oriented programming? Is it just a current buzzword, or does this approach appeal to you?

    Knuth: I've always thought of programming in that way, but I haven't used languages that help enforce the discipline; I've always enforced the discipline myself in other languages. Programming languages can now catch you if you make a mistake, and they make it easier for you to hide information from one part of the program to another. In my own programs, with older languages, I wouldn't use what I wasn't supposed to use; I would have to discipline myself to follow these rules. I could, so I did. There weren't programs I couldn't write... but the new tools do help.

    The problem that I have with them today is that... C++ is too complicated. At the moment, it's impossible for me to write portable code that I believe would work on lots of different systems, unless I avoid all exotic features. Whenever the C++ language designers had two competing ideas as to how they should solve some problem, they said "OK, we'll do them both". So the language is too baroque for my taste. But each user of C++ has a favorite subset, and that's fine. CWEB fully supports C++ as well as C.

    CLB: What are your thoughts about chaos theory, fractals, those areas? Their indeterminateness seems a little discordant with the domains you've focused on in the past.

    Knuth: I did some early work with fractals and so on, and I think it's a great new abstraction. People can build models that they wouldn't have thought of building before, that really match a lot of things in nature that have this character of looking the same when you change the scale. You know, if you magnify the coastline, it still looks like a coastline, and a lot of other things have this property. Nature has recursive algorithms that it uses to generate clouds and Swiss cheese and things like that. So now we have mathematical techniques for understanding such processes that go beyond the kind of differential equations that people used to have in previous centuries. Now we have a brand new tool to work with, but I'm not very intuitive about such methods. I know the limitations of my own intuition; I can solve some problems well, but I know other people are able to see something right away which takes me a long time... It's not my cup of tea.

    CLB: To what extent have you ever followed developments in artificial intelligence? The third program you ever wrote was a tic-tac-toe program that learned from its errors, and Stanford has been one of the leading institutions for AI research...

    Knuth: Well, AI interacts a lot with Volume IV; AI researchers use the combinatorial techniques that I'm studying, so there is a lot of literature there that is quite relevant. My job is to compare the AI literature with what came out of the electrical engineering community, and other disciplines; each community has had a slightly different way of approaching the problems. I'm trying to read these things and take out the jargon and unify the ideas. The hardest applications and most challenging problems, throughout many years of computer history, have been in artificial intelligence--- AI has been the most fruitful source of techniques in computer science. It led to many important advances, like data structures and list processing... artificial intelligence has been a great stimulation. Many of the best paradigms for debugging and for getting software going, all of the symbolic algebra systems that were built, early studies of computer graphics and computer vision, etc., all had very strong roots in artificial intelligence.

    CLB: So you're not one of those who deprecates what was done in that area...

    Knuth: No, no. What happened is that a lot of people believed that AI was going to be the panacea. It's like some company makes only a 15% profit, when the analysts were predicting 18%, and the stock drops. It was just the clash of expectations, to have inflated ideas that one paradigm would solve everything. It's probably true with all of the things that are flashy now; people will realize that they aren't the total answer. A lot of problems are so hard that we're never going to find a real great solution to them. People are disappointed when they don't find the Fountain of Youth...

    CLB: If you were a soon-to-graduate college senior or Ph.D. and you didn't have any "baggage", what kind of research would you want to do? Or would you even choose research again?

    Knuth: I think the most exciting computer research now is partly in robotics, and partly in applications to biochemistry. Robotics, for example, that's terrific. Making devices that actually move around and communicate with each other. Stanford has a big robotics lab now, and our plan is for a new building that will have a hundred robots walking the corridors, to stimulate the students. It'll be two or three years until we move in to the building. Just seeing robots there, you'll think of neat projects. These projects also suggest a lot of good mathematical and theoretical questions. And high level graphical tools, there's a tremendous amount of great stuff in that area too. Yeah, I'd love to do that... only one life, you know, but...

    CLB: Why do you mention biochemistry?

    Knuth: There's millions and millions of unsolved problems. Biology is so digital, and incredibly complicated, but incredibly useful. The trouble with biology is that, if you have to work as a biologist, it's boring. Your experiments take you three years and then, one night, the electricity goes off and all the things die! You start over. In computers we can create our own worlds. Biologists deserve a lot of credit for being able to slug it through.

    It is hard for me to say confidently that, after fifty more years of explosive growth of computer science, there will still be a lot of fascinating unsolved problems at peoples' fingertips, that it won't be pretty much working on refinements of well-explored things. Maybe all of the simple stuff and the really great stuff has been discovered. It may not be true, but I can't predict an unending growth. I can't be as confident about computer science as I can about biology. Biology easily has 500 years of exciting problems to work on, it's at that level.

    CLB: Use of the Internet is exploding right now, with everyone getting on...

    Knuth: Some day we are going to try to figure out who is paying for it!

    CLB: Do you currently use it? I know you did in the past.

    Knuth: I spent fifteen years using electronic mail on the ARPANET and the Internet. Then, in January 1990, I stopped, because it was taking up too much of my time to sift through garbage. I don't have an email address. People trying to write me unsolicited email messages get a polite note saying "Professor Knuth has discontinued reading electronic mail; you can write to him at such and such an address."

    It's impossible to shut email off! You send a message to somebody, and they send it back saying "Thank you", and you say "OK, thanks for thanking me..."

    Email is wonderful for some people, absolutely necessary for their job, and they can do their work better. I like to say that for people whose role is to be on top of things, electronic mail is great. But my role is to be on the bottom of things. I look at ideas and think about them carefully and try to write them up... I move slowly through things that people have done and try to organize the material. But I don't know what is happening this month.

    So now I don't read electronic mail, but I do use it occasionally. Say I'm taking a trip to Israel and I've got to make last minute arrangements. When I visit another university or research center for a few days, I have to send email from there. I've learned how to use the email facilities in Emacs, but I don't want to get good at it.

    CLB: You have many interests outside of computing and mathematics--- music, religion, writing. Is music a creative outlet for you, a means of recreation, or a spiritual outlet?

    Knuth: At the moment it's recreational. I like to have friends come to the house and play four-hands piano music. If I could do it every week, I would. I hope to live long enough so that after I've finished my life's work on The Art of Computer Programming, I might compose some music. Just a dream... it might be lousy music, of course.

    CLB: You have written some compositions already, haven't you?

    Knuth: Yeah, but it was mostly arrangements of other people's themes. I did write a short musical comedy when I was in college called "Nebbishland". Remember how Nebbishes were all the rage in the late 50s? "Nebbishland" was only about a ten minute skit, but it was all original music and lyrics.

    CLB: Do you have the score somewhere in the attic?

    Knuth: Yeah... no actually, I think I've lost it. I have only part of it. I'm hoping to come across it. I'm going through my files now and making a computer index of everything I have in the house.

    CLB: Sounds like you don't have a paperless house!

    Knuth: No!

    CLB: Have you fiddled with MIDI computer technology for music, or have you purposely stayed away from it?

    Knuth: I have fun with it. I bought a synthesizer for my son last Christmas, and I played it for hours and hours. I loved it. I had once played on a Kurzweil synthesizer years ago, at Marvin Minsky's house, a grand piano imitation. More recently, a friend went to England for three years and didn't want to bring his grand piano him, so he bought a Yamaha with six voices. When I visited his house, I had a tremendous time for three days going through all of the pieces I'd learned on the piano, playing them as if they were on vibraphone, or on a harpsichord, or some other voice. His "piano" has a harpsichord voice, but the keyboard is pressure-sensitive, so you can play loud and soft, which you can't do on a real harpsichord. These synthesizers are great.

    CLB: When did you retire from Stanford?

    Knuth: This year. I was on leave for two years until I could officially retire. Unofficially, I retired in 1990, on the same day I gave up email. I announced my plans three years earlier. I realized that my main goal in life was to finish The Art of Computer Programming; I had looked ahead and seen that it would take twenty years of work, full-time. If I continued doing everything else that I was doing, it was going to be forty or fifty years of work. I was just not getting anywhere, I was getting further and further behind. So I said, "Enough." Naturally, I hate to give up many of these other things that I like doing very much. But there are some things I didn't hate giving up, like writing proposals. I'm very happy to give up those!

    CLB: You had to write proposals?? I assumed you were insulated from that somehow.

    Knuth: You've got a great sense of humor! I don't have to do it anymore; but as a professor, in order to have decent equipment for my grad students, or to have visitors for active research programs, to publish reports, etc., I needed to find sponsors. It's a lot of work begging for money. The System Development Foundation said they'd give me a million dollars so that I could finish TeX and get back to The Art of Computer Programming.

    CLB: Did you take them up on it?

    Knuth: Sure, but it still took many, many years to finish TeX. I decided that the only way I would be able to finish The Art of Computer Programming is by going into full-time writing, and being a hermit, and telling people "No." It was hard to adjust the first couple of years. Now I feel real efficient, and the writing is going well. A nice steady state.

    I give lectures at Stanford every month or so, when I'm in town, called "Computer Musings" . I plan to keep this up for twenty years, to give a talk on whatever I find interesting that month, on neat ideas I've picked up... I bring up problems that I can't solve, so that somebody will do it for me. Now, if I can't solve a problem in two hours, I've got to give it up and tell somebody else to work on it; otherwise, I'll get behind again. As I write the book, I've got to move from topic to topic, and my attention span is maybe three weeks on any particular topic.

    CLB: You're best known for your writing and research; did you enjoy teaching and the interaction with students?

    Knuth: We had the greatest students in the world. I can still get together with students through my lecture series, except I don't know their names anymore. That's a problem.

    CLB: No student interns?

    Knuth: Suppose I give a "Computer Musings" lecture, stating an open problem, and suppose that a student in the audience solves that problem, writes his thesis and finishes it in the next two weeks (maybe two and a half), and shows it to me. Then I'd still be interested in the topic, would still read it, and I'd be glad to sign his thesis... but that's the only way. 28 is the total number of Ph.D. students I've had graduate, and that's probably all that I will have... unless something happens at high speed through the "Computer Musings".

    CLB: Real-time Ph.D.'s! What changes have you seen in the students coming into the computer science program over the years?

    Knuth: There is a very profound change that I can't account for. In the 70s, the majority of our students were very interested in music. The first thing we'd ask them when they came in was "What instrument do you play?" We had lots of chamber groups and so on. Now almost none of the students are interested in music. I don't know if it's because a different kind of people are enrolling in computer science, or because it's true of all today's students, or what. If you ask computer science students now what their hobby is, the chances are most of them will say "Bicycling". I recently had one who played a harmonica, but there were almost no musicians in the group.

    CLB: Any changes in the quality of the students?

    Knuth: Not the quality... but they don't know as much about mathematics as they used to. We have to do more remedial stuff in college, even at a school like Stanford.

    CLB: How about changes in the field itself... with so much progress and so many more people involved, is computer science today very different than it was earlier?

    Knuth: Well, there's all the media and the visual things, that's a lot different than it was. There's also the competition; it's a great deal more difficult now than it was in my day. When I started, it was so easy to come up with something new compared to now, when you've got thousands and thousands of smart people all doing great stuff. There might have been ten great Ph.D. theses a year at one time; there's just no way to keep up with all the stuff now.

    No matter what field of computer science you're in, everyone is finding it hard to keep up. Every field gets narrower and narrower, since nobody can cover all the territory anymore. Everybody can choose two small parts of computer science and learn those two parts; if one person knows parts A and B, another knows B and C, and another knows C and D, the field remains reasonably well connected, even as it expands.

    CLB: Do you see yourself as one of the last of computer science's "Renaissance Men"?

    Knuth: I'm not as broad as you might think--- I only work on one thing at a time. I guess I'm a quick study; I can become an instant expert in something. I've been collecting stuff for thirty years so that I can read the literature on each topic in "batch mode"--- not swapping lots of different topics in and out. I can absorb a subject locally and get good at it for a little while... but then don't ask me to do the thing I was doing a few months ago! Also, I have lots of people helping me correct my mistakes.

    CLB: My last question, your least favorite to be asked... what is the current plan for completing all seven volumes of The Art of Computer Programming?

    Knuth: I'm going to have fascicles of about 128 pages coming out twice a year. We're gathering four of them before we come out with the first two actually; we're going to keep some in the pipeline! Look for the first fascicles in 1995 or 1996; they will be beta-test versions of the real books. I'm thinking I can finish Volume IV (parts A, B, and C)in the year 2003, Volume V in 2008, then come out with new editions of Volume I, II, and III, then work on VI and VII... There will be a "Reader's Digest" version of volumes I through V.

    CLB: What would your career, and life, have been like had you not announced the 7-volume set?

    Knuth: Oh, I didn't announce it at first. I thought I was writing only one book. But if I hadn't done that, I suppose I still would have been doing a lot of writing. Somehow it seems that all the way through, I've enjoyed trying to explain things. When I was in high school, I was editor of the student paper; in college I edited a magazine. I've always been playing around with words.

  • by spotter (5662) on Saturday March 16, 2002 @11:07PM (#3175653)
    Acrobat works fine in linux. I'm currently using the plugin in galeon and it displays fine. No need to use windows.

    Here's another mirror
    http://www.cs.columbia.edu/~spotter/fea-kn uth.pdf
  • Mirrored here (Score:3, Informative)

    by Quixote (154172) on Saturday March 16, 2002 @11:16PM (#3175685) Homepage Journal
    Finally managed to download it.
    Grab a copy from here [buffalo.edu]
  • by Lictor (535015) on Sunday March 17, 2002 @12:33AM (#3175846)
    >but the only game in town (for mathematics or anything)? No, not really.

    I can't speak for general publishing, but for serious math publishing I have to respectfully disagree. If you have ever even remotely come into contact with serious mathematics you will be aware that Springer-Verlag (http://www.springer.de/) is one of the major publishers.

    I have never prepared a manuscript for a Springer book or journal that was *not* in TeX format.

    Could you give me some examples of the "quite a lot of software used before latex"? Specifically what "math" publishers use standards other than TeX... I'd truly be interested because I've never come across one.

    As a side note, please be careful not to confuse LaTeX with TeX. LaTeX (which I admit to using most of the time) is kind of like "TeX for dummies". (Thats not entirely fair... LaTeX makes 95% of what I want to do easier and faster than plain TeX... but for that last 5%, LaTeX makes me want to punch things. LaTeX=easy, TeX=flexible).
  • by sh0rtie (455432) on Sunday March 17, 2002 @12:43AM (#3175860)


    http://access.adobe.com/adv_form.html

    just enter the url of said pdf and hit submit and voila good ol' html is returned
  • by sunhou (238795) on Sunday March 17, 2002 @01:48AM (#3175985)
    Apparently Richard Feynman, on the last day of classes each semester, made the class an optional thing where students could come and ask questions on any topic except religion, politics, and the final exam. And Knuth followed his example.

    Now that I'm teaching, I'm thinking of trying that. I can't decide if I really want to exclude religion and politics, though. I wonder if they excluded those topics to avoid offending people, or because they thought those topics are too subjective/personal, or if it was for some other reason?

    I also wonder if anyone would come on that day; the last day of classes in the spring at Cornell is "Slope Day", where all the undergrads hang out on the hill by the main library and get drunk (the police basically look the other way, as long as people aren't getting hurt). It's truly a sight to behold.
  • by bentini (161979) on Sunday March 17, 2002 @02:40AM (#3176070)
    No. My dad (a fairly amazing computer scientist himself) threatened to disown me if I cashed my Knuth check.
  • by Trepidity (597) <delirium-slashdo ... org minus author> on Sunday March 17, 2002 @04:02AM (#3176189)
    MathML is intended to be such. Without some additional formatting work it wouldn't be a good typesetting language though, as (in the tradition of HTML) it merely specifies the mathematical formulae, leaving their exact rendering up to the browser (while for typesetting you probably want some more exact control).
  • by billstewart (78916) on Sunday March 17, 2002 @04:37AM (#3176237) Journal
    If MathML does a good enough job, and is supported well enough by popular browsers, that's fine - it's the proper approach according to the SGML religion that led to HTML. That way, the browser can respond not only to user preferences, but to the limitations of the display - if it's a clumsy display, the fine tweaking you did is wasted and may make things worse.

    As an example of what can go wrong, look at your average TeX-written math/cs paper on your average PC screen. The font's too grainy and greeky to read at 75-100dpi, and it's probably in some two-column format that looks really nice printed on portrait-mode dead trees, but is horrendously annoying to read on a portrait-mode screen that can only display about half a paper page at bad resolution. Arrrgh!

    Somebody once commented that there are better renditions of the TeX fonts for PCs - I think it was a TrueType implementation of CMR fonts or something, but it's been too long to remember the correct details.

  • Re:The right answer. (Score:2, Informative)

    by fcanedo (553180) on Sunday March 17, 2002 @06:15AM (#3176332)
    Contrary to what some people seem to think, 42 is not the answer to any question.

    It is the answer to 'the question of life, the Universe and everything'. Now what that question is exactly... no one knows! ;)
  • LaTeX and PDF (Score:3, Informative)

    by borud (127730) on Sunday March 17, 2002 @11:10AM (#3176723) Homepage
    As an example of what can go wrong, look at your average TeX-written math/cs paper on your average PC screen. The font's too grainy and greeky to read at 75-100dpi [...]

    I usually generate two outputs of my LaTeX documents: Postscript and PDF. The PDF version usually looks a bit better on screen than the PostScript version.

    mind you: I generate the PDF version using pdflatex . I can't remember exactly, but I think I've seen a utility that converts DVI files to PDF and that this produced horrible output. use pdflatex .

    because generate multiple output formats (PS, PDF and HTML) from the same LaTeX document, I usually use a package I wrote that contains a lot of convenient macros to make use of the different features in the different formats -- in addition to automating a lot of boring tasks.

    I remember how delighted I was when I discovered pdflatex. once you work it into your repertoire you get all this cool stuff for free, like hyperlinks in PDF documents etc. I really recommend you give it a try.

    Check out the PDFTeX [tug.org] web page for more information.
    Also have a look at Matt Welsh' page about creating presentations in PDFLaTeX [berkeley.edu]. He has some useful information on how to install TrueType fonts for use by PDFLaTeX.

    -Bjørn

  • by FFFish (7567) on Sunday March 17, 2002 @02:34PM (#3177269) Homepage
    Ventura Publisher, according to this history [dtp-service.com], was released in April, 1986, by a group of Xerox employees who couldn't get that company to get a clue.

    Same year as LaTex, and with a GUI to boot.

    Still around, still in active development (new release has been mentioned by Corel), and still the best layout application that is available, bar none. Even four or five years after its last release, it still does things that InDesign and Quark don't.
  • Re:LaTeX and PDF (Score:2, Informative)

    by The Musician (65375) on Sunday March 17, 2002 @08:09PM (#3178443) Homepage
    You can also just use the program dvipdfm, which does the right thing with eps files, and most other things. It is an easy way to make PDFs from TeX that people can actually read.
  • Re:LaTeX and PDF (Score:2, Informative)

    by Liam (39474) on Monday March 18, 2002 @12:48AM (#3179493)
    Have you seen PDFScreen [tex.ac.uk]? Look at the screen formatted manual [tex.ac.uk] then at the the print form [tex.ac.uk]. You might change your mind. I think a lot of the readability of the screen form is in using non-cmr fonts, which unfortunately are not specified. I wish there were a guidebook to TeX fonts, in the manner of the "Companion" series of LaTeX books!

Often statistics are used as a drunken man uses lampposts -- for support rather than illumination.

Working...