Welcome to Math 29.

There are no prerequisites for this course, other than a willingness to learn, and in particular, to learn how to write proofs. I do not expect you to be an expert proof writer at the beginning of the class.

This course is an introduction to recursion theory, also known as computability theory, a dynamic area of contemporary research with consequences for the foundations of mathematics, and for theoretical computer science. Recursion theory is concerned with the nature and structure of computable functions, i.e. those functions whose output can be determined by a finitary program. (A program taking finitely more machine space than we currently command is finitary, while a program that requires infinite capacity is not). The class will formalize several notions of computability, and consider their relationship to each other. We will discuss Church's Thesis, which equates these formalizations with intuitive notions of computability. We will examine functions which are, and are not, computable. Some functions are not computable by any means whatsoever; this is linked to incompleteness phenomena via the Halting Problem. We will then study selected topics relating to computability, as time permits.