Stephen Cole Kleene.


Recursion theory, Spring 2008

Instructor: Christian Rosendal, room 304 Altgeld Hall

Course hours: 9:00 AM - 10:20 AM Tuesday and Thursday
Location: Room 345 Altgeld Hall

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:

  • Primitive recursive and partial recursive functions.
  • Arithmetisation and the recursion theorem.
  • Recursive and recursively enumerable sets.
  • Hilbert's 10th problem.
  • Kolmogorov complexity.


    • 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.
    Some notes

  • The Kucera - Gacs Theorem.
  • The jump operator.
  • Plain complexity and randomness.
  • Relativised computability.
  • Infinite games and measurable cardinals.


    • Required reading:
  • Course notes on recursion theory. Available here.

    • Other suggested reading:
  • Hartley Rogers: Theory of recursive functions and effective computability.
  • Harry R. Lewis and Christos Papadimitriou: Elements of the theory of computation.
  • R.I. Soare: Recursively enumerable sets and degrees.
    • Back to Christian Rosendal's homepage.