Tuesday, May 20, 2014

20 Questions for Donald Knuth

Here is an interesting and good* interview with Donald Knuth, in which he is asked twenty questions and he responds. This is to celebrate the electronic version of The Art of Computer Programming.

* Here I am using the Alf van der Poorten definition of "good". A "good" interview is one in which I am mentioned.


lukebarnes said...

Great stuff. Two things:

1. What did you think of his answer to your question? I find it very interesting that he thinks that a computer could identify the "aha moments" in a "mechanically discovered proof". How do you teach a computer to teach us how it proved something?

2. As someone who is neither mathematician or computer scientist, but spends a large part of his day programming none-the-less, Knuth's 3,000 page book is rather intimidating. I know from its legendary reputation that it remains a gold mine (http://recursed.blogspot.ca/2008/01/donald-knuth-and-me.html)? Can I just dip in on subjects of interest? Should I just get Volume 1 and start ploughing through?

IThinkWithMy Liver said...

Sorry to ask an unrelated question, but, what is the current status (2014 May 21) of the twin primes conjecture? What is the smallest fixed gap size between infinitely many pairs of primes that has been proved to exist?

crf said...

70 million.
Yitang Zhang

Jeffrey Shallit said...

No, that's not right, crf. The current best bound is 600. See

http://arxiv.org/abs/1311.4600 .

IThinkWithMy Liver said...

My apologies: not sure where to post this link:


But it's damned funny! :)

Jeffrey Shallit said...


1. Some remarks: from Goedel we know that there are many statements that are true but unprovable. Furthermore if various complexity hypotheses turn out to be true, then there will be lots of easy-to-state problems that have no short proofs. See, e.g., http://www.math.ucsd.edu/~sbuss/CourseWeb/Math268_2014W/BeamePitassi_pastpresentfuture.pdf .

Roughly speaking this means that there many things that are true, but "for no good reason".

Dyson gave a possible example: there are no powers of 2 whose reverse (considered as a number in base 10) is a power of 5. See, e.g.,
https://www.cs.auckland.ac.nz/~cristian/fdyson.pdf .

So in general I think it is hopeless to maintain that most of the things we want to prove will have simple and comprehensible proofs.

As for "aha" moments, I think there is no "in principle" barrier to this, but it will require a better understanding how humans "understand" things than we have now. It is also likely to be very individual - some combinatorialists are convinced more by generating functions and some more by bijective proofs.

2. Yes, you can certainly just browse the books at your leisure. For my taste, the most interesting things are in volumes 1 and 2, but I haven't read much of volume 4 yet. But don't waste any time learning MIX.

Jeffo said...

Re: automating "aha" moments, chess.com has developed some kind of automated method for mining games played between humans to find positions to use in their "Tactics Trainer", which drills basic chess tactics like sacrifice, decoy, pinning, etc. These often involve what feels like (for me) moments of deep insight.