Notes on a Conversation with Donald Knuth

Donald Knuth chatting at UBC
Donald Knuth chatting at UBC

So I had the privilege of seeing Donald Knuth speak at UBC a few days ago. I was excited to see one of the eccentric Computing Science legends in real life.

The talk was in an interesting format. Knuth was in front of a relatively small theater, and simply answered any questions that were presented to him from the crowd. It was thus a spread of different questions and topics presented to him.

I took a few notes during the talk and I summarize the topics and Knuth’s responses here.

Knuth on writing:

  • translate to have less jargon
  • pays people to find errors in his books
  • write to have errors, that is, be precise and falsifiable (e.g. “13% improvement”, where this 13% can be verified)
  • have the history of discoveries with references
  • write about things that will be important 50 years from now
  • –> e.g. methods that are useful for many different applications
  • –> e.g. data structures, satisfiability problems

Knuth on AI

  • “more power to it”
  • accept it
  • extend our capabilities with machines

Knuth on the coming Singularity:

  • the Singularity is always 10 years from now
  • did not have too much to say on developments in AI

Knuth on people who look up to him for his opinions on non-CS issues (e.g. politics):

  • good CS writer, but not entirely comfortable with others relying too much on his non-cs writing
  • should think for oneself and not just take his opinion

Knuth on his belief that probably p = np:
(I had to double check that I heard this right, and I found a talk here where he confirmed this belief.
I really did not follow his reasoning… something about there being many algorithms and we had not found it yet… )

Knuth on if we have found all the simple relatively small algorithms e.g. quicksort:

  • he still sees a lot of new elegant and important algorithms being proposed

Knuth on Bill Joy and Danny Hillis’s talk on the “Coming Entanglement“:

  • hard for humans when complexity increases
  • dangers of writing software without understanding it
  • many times when mathematical proofs come out, there are errors

Knuth on how to be a prolific writer and choose good research problems:

  • there are many hours in a week to work…
  • choose research based on own instincts rather than what others want you to work on or trends
  • –> if too many other people are working, starts to wonder if was a good thing to do
  • “life is a binary search”
  • could not write software and teach classes at the same time
  • –>could teach and write papers, but not teach and write software

Knuth on his education:

  • choose to study physics over music since the physics program was said to be harder
  • –> then switched from physics to math since he was not very good at the labs in physics
    (nice to hear that someone as smart as Knuth has troubles with certain topics)

Knuth on music:

  • some type of music sharpens or decreases focus on certain tasks
  • is writing music based on a system of constraints

Knuth on quantum computing:

  • did not have much to say

Knuth on how to convey to a non-programmer the beauty of code:

  • might not be possible
  • “my wife doesn’t get it” (joking)

Knuth on if we should index arrays from 0 or 1:

  • depends on problem and switches between both in his book (or upcoming book?)
  • some problems work out nicely if we start with 0
  • sometimes nice to have 0 as a sentinel

Knuth on being stumped on problems:

  • can get stumped and give up, then a week later an idea suddenly comes
  • sometimes gets stumped and still has not been solved

Knuth on working:

  • sometimes has to get psyched up to get started
  • all tasks being equal, he will do the thing he likes the least to do
  • –> this way always gets stuff out the door and not just gratifying oneself

Knuth on automation:

  • good way to learn about a problem is trying to simulate it
  • hesitate to use the actual automation, but is good to learn