Recursion Theory

Course manual 2024/2025

Course content

The basics of recursion theory: the notion of algorithm and its formalization, limitative theorems; and their application to the foundations of mathematics (Gödel's Incompleteness Theorem). In addition, Turing degrees and the arithmetical hierarchy will be introduced.

Study materials

Literature

• Syllabus Computability Theory. Sebastiaan Terwijn. [https://www.math.ru.nl/~terwijn/teaching/syllabus.pdf]

• Gödel's Incompleteness Theorems – Lecture Notes. Stefan Hetzl. [https://dmg.tuwien.ac.at/hetzl/teaching/git_2024.pdf]

Objectives

• Understand several formalizations of algorithms (partial recursive functions, partial computable functions)
• Be able to show whether (and how) a given function or relation is primitive recursive, computable, or recursively enumerable
• Understand how complex objects (sequences, trees, computations) can be encoded into natural numbers in a primitive recursive way
• Be able to show how to encode (new) objects into natural numbers in a primitive recursive way
• Understand foundational results in the theory of computability (e.g., the Normal Form Theorem, the Enumeration Theorem, the Recursion Theorem)
• Understand limits on computability (i.e., uncomputability)
• Be able to show that a given function is uncomputable
• Understand the Arithmetical Hierarchy and how it can be used to assign complexity levels to functions, sets, relations
• Be able to characterize the complexity of a function in terms of the Arithmetical Hierarchy
• Understand the notion of Turing degrees and how it provides a hierarchy of complexity
• Understand the statement of Gödel's Incompleteness Theorems
• Be able to explore and explain the (philosophical and mathematical) implications of Gödel's Incompleteness Results
• Understand the proof of Gödel's First Incompleteness Theorem, and the main working of the proof of Gödel's Second Incompleteness Theorem

Teaching methods

• Lecture
• Seminar
• Self-study

In the lectures, we will cover the main theoretical tools that are used. In the exercise sessions, students will engage with the material in order to deepen their understanding.

Learning activities

Attendance

This programme does not have requirements concerning attendance (TER-B).

Additional requirements for this course:

There is no mandatory attendance.

Assessment

Assignments

The homework assignments may be done individually or in pairs. All assignments are graded. Feedback on the homework assignment is given via Canvas.

Fraud and plagiarism

The 'Regulations governing fraud and plagiarism for UvA students' applies to this course. This will be monitored carefully. Upon suspicion of fraud or plagiarism the Examinations Board of the programme will be informed. For the 'Regulations governing fraud and plagiarism for UvA students' see: www.student.uva.nl

Course structure

Additional information

Recommended prior knowledge: Basic logic and some mathematical maturity. Students in doubt are encouraged to consult the teacher in advance.

Contact information

Coordinator

• dr. Ronald de Haan

Staff

• Tenyo Takahashi