COLLOQUIUM Department of Computer Science and Engineering University of South Carolina Gödel for Geeks: the Incompleteness Theorem in a Nutshell Stephen Fenner Department of Computer Science and Engineering University of South Carolina Date: October 3, 2003 (Friday) Time: 3:30-4:30PM Place: Swearingen 1A03 (Faculty Lounge) Abstract Time Magazine recently listed Gödel's incompleteness theorem as one of the greatest intellectual achievements of the 20th century. The theorem states that any reasonable mathematical theory must contain statements that can be neither proven nor refuted. The disturbing possibility that many unsolved mathematical problems (and we cannot tell which) must remain unsolved forever has deeply affected the foundations of mathematics. Despite its significance, Gödel's theorem is quite simple and intuitive at its core. I will present a short proof of the theorem, based on a few elementary and reasonably evident facts about computer programs and their behavior. Stephen Fenner (email: fenner@cse.sc.edu, homepage: http://cse.sc.edu/~fenner) is an Associate Professor of Computer Science and Engineering at the University of South Carolina. He has a BA in Physics from Harvard and an MS and a PhD in Computer Science from the University of Chicago. His research is primarily in theory, with particular interest in computational complexity, computability, quantum information processing, and computer security. His chief time-wasting "research" hobby is in the foundations of mathematics.