Can computers do real math

25 September 2013 by Guest blogger, posted in General





The HLF event started on Sunday September 22, 2013 with formal introductions of the laureates, followed by informal mingling between the young researchers and the laureates, and finally ended in a musical play which provocatively posed the question "Can computers ever become good at tasks like producing music that seem to require taste, creativity and emotion?" The entire play was in German with an orchestra in the background playing musical pieces composed by Mozart. There were two protagonists, a man and a woman. The man argued that computers are incapable of creating sublime music like Mozart, while the woman forcefully argued in favor of computers being able to create great music. To prove her point, she demonstrated a program, which stitched together random snippets of Mozart’s music selected by the audience that sounded like, well, Mozart. She also subjected the male protagonist to a "Turing test", where the question posed to him was "Following are two pieces of music played by an expert pianist. Tell us which one was written by Mozart and which generated by the computer?" Apparently, both were computer generated.




Raj Reddy’s Talk on "Who Invented the Computer?"

Professor Reddy (Turing Award) from CMU gave a fascinating account of the history of computing from Leibnitz to Turing. He gave a very comprehensive multi-dimensional criterion for deciding who invented the computer "as we know it today." The criteria included dimensions like "Did person X design a general-purpose programmable design for the first time," "Did their design include the idea of stored programs," "Did it have jump and conditional branching," and "Did the inventor actually manage to build a prototype" (Babbage gets eliminated on this one).


Curtis T. McMullen’s talk on "Billiards in moduli space" (Math)


Steve Smale’s talk on the Protein-folding Problem (Math)

Steve Smale (Fields Medalist) from the City University of Hong Kong and Berkeley gave an account of the math behind the protein-folding problem and how his group has developed award-winning algorithms that can predict the folding of proteins. The problem is "Starting from a sequence of letters representing the amino acids in a protein, can you predict the final 3D structure of the protein".  The math required to model this problem is probably not that complicated, but coming up with efficient algorithms and their implementation is highly non-trivial.





A question that repeatedly came throughout the many talks, informal discussions and panel was "can computers do real math," a question is directly addressed in the context of formal methods of verifying program correctness (I discuss this question later on).

Leslie Valiant’s talk on Learning as the Source of Life Phenomena

Leslie Valiant (Turing Award) from Harvard gave probably the most interesting talk of the first day on how computational learning theory can be applied to "explain evolution". The problem that he addresses is that if you simply assume a Darwinian model of random mutations and the survival of the fittest, it doesn’t explain how evolution occurred in a "mere" 4 billion years (the Universe itself is believed to be around 13.7 billion years old). According to Valiant, Darwin’s theory is only an outline and not a theory in the sense of a theory of physics with a precise mathematical description and predictive power.

In order to cast something as a machine-learning problem one has to have a target function. Valiant proposes that the target function in this case is an "ideal function" that indicates the optimal behavior (output of a the circuit being learnt) in any possible environmental condition.  The question of how quickly life evolved can be now analyzed using complexity-theory, and we can ask whether a target function representing the "survival of the fittest" can be "learnt easily."


The panel discussion was inspiring, touching on questions/topics such as "how to do research" (Ed Feigenbaum) to "can computers be used to construct mathematical proofs" (Lampson and Shafi) to the "evolution and acceptance of provable cryptography by both engineers and mathematicians" (Shafi).




Courtesy of Vijay Ganesh


Origin of this blog post

Leave a Reply

seven − 6 =