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.
Great stuff. Two things:
ReplyDelete1. 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?
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?
ReplyDelete70 million.
ReplyDeleteYitang Zhang
http://en.wikipedia.org/wiki/Yitang_Zhang
No, that's not right, crf. The current best bound is 600. See
ReplyDeletehttp://arxiv.org/abs/1311.4600 .
My apologies: not sure where to post this link:
ReplyDeletehttp://www.nature.com/news/publishers-withdraw-more-than-120-gibberish-papers-1.14763
But it's damned funny! :)
Luke:
ReplyDelete1. 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.
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.
ReplyDelete