Proofs and Computation

Madhu Sudan (Harvard University)

Proofs have always gone hand in hand with the development of (the theory of) computation. The Turing Machine was conceived to generalize and extend Godel's incompleteness theorem. The P vs. NP question emerged in part out of an effort to understand the complexity of theorem-proving. And modern theories of optimization and cryptography are intimately tied to novel notions associated with proofs such interaction and randomness. In this talk we will survey some of these classical connections as well as the more modern ones; and ponder some, as of yet unresolved, enigmas associated with proofs we use in day to day (mathematical) life.