Objectives
Understanding the key concepts and some basic methods of modern recursion theory.
Contents
This lecture course will cover the basics of recursion theory: the notion of algorithm and its formalization, limitative theorems; and discuss the connections between recursion theory and the foundations of mathematics (Gödel's Incompleteness Theorem). After that, Turing degrees and the arithmetical hierarchy will be introduced.
Recommended prior knowledge
Basic logic and some mathematical maturity. Students in doubt are encouraged to consult the teacher in advance.
Registration at
Registration for courses is mandatory, but will be done by the Education Service Centre for the 1st year MSc students for courses of the first semester. See also
http://www.student.uva.nl and choose your master and then 'New procedure 'Registration for courses Faculty of Science'.
Format
Lectures and Exercise Sessions.
Study materials
The course will be based on a preliminary version of
Computability Theory and Applications, by Robert I. Soare, to be made available to the participants. Moreover, fairly extensive lecture notes will be provided. Soare’s book is to replace his Recursively enumerable sets and degrees. For a less abstract, and, in a sense, less casual approach, it may be useful to study Cutland’s
Computability or Cohen’s
Computability and Logic by the side.
Assessment
Homework; final exam.
|