UvA Logo

Advanced Topics in Recursion Theory
2004/2005; 2nd Semester
Institute for Logic, Language & Computation
Universiteit van Amsterdam

Instructor: Dr Benedikt Löwe
Vakcode: MolATRT6
Time: Thursday, 17-19
Place: P.018
Grader: Dipl.-Math. Stefan Bold (sbold (at) science.uva.nl)
Course language: English
Intended Audience: M.Sc. students of Logic and Mathematics
Prerequisites: "Recursion Theory" (as taught in the first semester); the basic theory of Turing degrees and recursively enumerable sets.

This course will start where Recursion Theory ended in the first semester: with the Kleene-Post theorem (Theorem 10.6.3 in Cooper's book). Starting from there, we shall discuss more advanced recursion-theoretic constructions (finite injury arguments and infinite injury arguments) and then discuss some ideas of infinitary computation.

Literature: Barry Cooper, "Computability Theory" (Chapters 10, 12, 13 and 14). We will sell the book to enrolled students for EUR 32 in the break of the first lecture (at a substantial discount compared to the list price of $69.95). Several papers on Infinite Time Turing Machines will be handed out in class.


Last update : May 19th, 2005