Ah, but a man's reach should exceed his grasp, or what's a heaven for?
Robert Browning, Andrea del Sarto
Math 29: Introduction to Computability
- Instructor: Rebecca Weber
- Office hours Thursdays 1-3 and by appointment in Kemeny 317
- Class meets MWF 11:15-12:20, X-hour (to be used rarely, if ever) Tu 12:00-12:50; Haldeman 028 Syllabus (pdf)
- Course notes are available through the Copy Center. Topics and Resources Errata
Homework Assignments
Term Paper Topic Ideas
First draft and final version of sample paper on the Recursion Theorem.
Pdf and tex of symbols useful for your term papers. See the bottom of this page for links to other useful tex documents.
What is computability? That is the first question we will try to answer. We'll discuss a few formalizations of computability, two in more depth and the rest just in passing, and the surprising fact that they define the same collection of functions, which we call the computable functions. We'll discuss why this seems like a reasonable title for them, though we could never prove they are the correct collection.
Once that's under our collective belt, we'll see what it leads to. Are there noncomputable functions, and if so, how can we specify them if they're noncomputable? If we assume we magically have the ability to compute one of them, what additional computational power does that give us? We'll try to finish with a survey of some areas of currently active research, just to get a sense of what the field is about today.
There are no prerequisites for Math 29. We will cover background material as needed and when relevant, and as long as you're willing to learn to work abstractly and to read and write proofs, you are sufficiently prepared!
- Slides from the first day's course overview
- Slides from a similar but longer talk I gave to an undergraduate audience at MIT in early March
Last modified May 21, 2009