Math 29: Topics

This list is drawn from the table of contents of the course notes. I will try to add links to useful resources when I find them.

• Defining computability
  • Turing machines
  • Partial computable functions
  • The Church-Turing thesis
• Working with computable functions
  • Coding and countability
  • A universal Turing machine
  • Parametrization and the recursion theorem
  • Noncomputable functions and the halting problem
  • Undecidability
• Computable and computably enumerable sets
• Turing reduction, Turing degrees
• Areas of research
• Randomness
• Computable model theory
• Reverse mathematics

Back

Last modified April 1, 2009