Stephen Cole Kleene.

**
Recursion theory, Spring 2008
**

This is the basic course in recursion or computability theory. The development of recursion theory is closely tied to the study of decision problems in logic in the beginning of the century and to Goedel's Theorem. We shall study some of the basic theory, its connections with decision procedures in algebra and number theory and also a topic of high current interest among recursion theorists, namely, Kolmogorov complexity. Main themes:

The course will not require any specific knowledge, but familiarity with logic or computer science can be useful. The second part of the course will involve some elementary number theory and the third part some very basic measure theory.

Required reading:

Other suggested reading:

Back to Christian Rosendal's homepage.