Math Colloquium

Math Colloquium

(Distinguished Speculative First of April Talk)

Speaker: Scott Aaronson, MIT

http://scottaaronson.com/

Title: How Pervasive Is Incompleteness?

Abstract: I was asked to give a “speculative” math talk. So, I'll discuss the question of just how much “normal, finitary” math the Gödel incompleteness phenomenon might infest. I’ll first survey the types of independence and undecidability results that are known, and explain why in my view, none of them give a fully satisfactory answer. I’ll then speculate about the question, which I’m often asked, of whether the P vs. NP problem might turn out to be formally undecidable. Finally, I’ll discuss the Busy Beaver function, and its amazing ability to “concretize” questions of mathematical logic. I’ll mention some ongoing work with Adam Yedidia that aims to construct a small Turing machine whose (non-)halting is provably independent of the ZFC axioms.

Short Bio: Scott Aaronson is an Associate Professor of Electrical Engineering and Computer Science at MIT. He studied at Cornell and UC Berkeley, and did postdocs at the Institute for Advanced Study as well as the University of Waterloo. His research focuses on the capabilities and limits of quantum computers, and more generally on computational complexity and its relationship to physics.  His first book, Quantum Computing Since Democritus, was published in 2013 by Cambridge University Press. Aaronson has written about quantum computing for Scientific American and the New York Times, and writes a popular blog at www.scottaaronson.com/blog. He’s received the National Science Foundation’s Alan T. Waterman Award, the United States PECASE Award, and MIT's Junior Bose Award for Excellence in Teaching.