Computability Theory, Spring 2013
This course is part of the Mastermath programme.
Lecturer is Jaap van Oosten.
Exercise class assistant is Eric Faber (e.e.faber AT students.uu.nl).
This course will be given in weeks 6-21 (February-June 2013).
The course is on Mondays, 10:15-13:00, in Ruppert Building (Leuvenlaan 21, next to Educatorium): first lecture in room 116; all other lectures in room B.
The course will be concluded by a written exam. There are, during the course, 6 hand-in exercises, which may count for 30% of your final grade (it is not compulsory, although strongly recommended, to hand in these exercises). That is, your final grade will be calculated as follows: let H be your grade for the hand-in exercises and W your grade for the written exam. Your final grade will be the maximum of W and the number (3H + 7W)/10.
The hand-in exercises have to be handed in at the exercise class in the week they are mentioned below.
Here are model solutions for the hand-in exercises. These will appear a week after they were due.
Literature: We use Lecture Notes for the course.
Overview of the material treated in the course
Not always there will be time enough to treat all material in the lecture. What is listed is the required reading for the exam.
- Week 6: Introduction, Register Machines and Computable Functions
- Week 7: Primitive Recursive Functions and Coding of Sequences
- Week 8: Partial Recursive Functions, Coding of Programs and Computations: Partial Computable=Partial Recursive
Hand-in exercise: 21
- Week 9: Smn-Theorem and Recursion Theorem; unsolvable problems.
- Week 10: Recursively enumerable sets; recursively inseparable r.e. sets; Kleene tree.
Hand-in exercise: 35
- Week 11: Myhill-Shepherdson-Rice-Shapiro.
- Week 12: Remainder of Chapter 3: Friedberg and Kreisel-Lacombe-Shoenfield.
Hand-in Exercise: 55
- Week 13: Many-one Reducibility and Arithmetical Hierarchy.
- Week 14: No Lecture (Easter Monday)
- Week 15: No Lecture (Lecturer sick)
- Week 16: Section 4.2.1: some exact classifications.
Hand-in Exercise: 72
- Week 17: Section 4.3.
- Week 18: Chapter 5: Relative Computability, until Theorem 5.2.5.
Hand-in Exercise: 77
- Week 19: Rest of Chapter 5; 6.1,6.2.
Hand-in Exercise: 87
- Week 20: 6.3, 6.4.
- Week 21: No Lecture (Whitsun Monday)
- Week 22: Exam Monday May 27, 16:00--19:00, Buys Ballot Building 065
- Week 25: Retake exam Monday June 17, 16:00--19:00, Buys Ballot Building 005
Registration for the retake exam is required! Send an e-mail to me, j.vanoosten@uu.nl, before June 10, if you wish to take part in the retake exam.
- Exam April 2002 (Dutch), with solutions (in Dutch).
Exam July 2002 (Dutch), without solutions.
Exam March 2007, without solutions.
Exam January 2012, without solutions.
Exam May 27, 2013, with solutions.
Back to my teaching page