NMAK24006U Computability, Turing Machines, and Gödel's Incompleteness Theorems

Volume 2024/2025
Education

MSc Programme in Mathematics
MSc Programme in Mathematics with a minor subject

Content

This course is an introduction to computability theory and Gödel's incompleteness theorems.

The first half of the course will focus on computability theory, and will include: Recursive and primitive recursive functions, Turing machines and computable functions, basic results in computability theory including Kleene's Normal Form Theorem, the s-m-n Theorem, Kleene's Recursion Theorem, Recursively enumerable sets, the halting problem and decision problems in general. If time allows, we'll also look at hierarchy theory, relative computability, and Turing degrees.

The second part of the course will focus on Gödel's first incompleteness theorem, and will include: Axiom systems for number theory, representable relations and functions, arithmetization of syntax, the Fixed-Point Lemma, and Gödel's first incompleteness theorem. If time allows, we'll also look at Gödel's second incompleteness theorem.

During the last 3 weeks of the course, the participants will work on an invidivual written project on a topic related to the course content described here. The lecturer will help the students find a relevant topic to focus on for the project part.

Learning Outcome

Knowledge: 
The participants are expected to acquire the knowledge listed above in the course description.

 

Skills: 
The participants are expected to be able to show that various basic number-theoretic functions are computable, by showing that it can be computed on a Turing machine and by showing the function is recursive, using the definitions as well as the theorems listed in the course description. The participants are expected to know how to use computable functions to arithmetize syntax and syntactical notions of formal logic, as it is used in the proof of Gödel's first incompleteness theorem.

 

Competences: 
The participants are expected to master the fundamentals of computability theory and how this is applied to undecidability and incompleteness problems.

Please look on Absalon ahead of the start of the course for precise information about course literature.

For some parts of the course, we may use parts of Chapter 3 in H. Enderton's "A mathematical Introduction to Logic", which is the same book where Ch. 2 is used in the course Introduction to Mathematical Logic (block 3).

You must have taken the course "Introduction to Mathematical Logic", or a similar logic course, to take this course. In particular, you must have previously had a proper course in formal first order predicate logic (i.e., formal logic with quantifiers).
Please note: If you have only seen logic based on truth tables (i.e., sentential or propositional logic), or you have only seen an informal introduction to predicates and quantifiers (such as in the course DisMat), then you _do not_ have sufficient background to take this course.
If you have not taken "Introduction to Mathematical Logic", please read the course description of that course to be sure you have the right background.
Contact the course responsible before signing up if you're not sure you have the right qualifications.
4 hours of lectures, 2 hours of tutorials for 6 weeks, followed by 3 weeks of project writing.

Note that the lectures will be given in a combination of different formats: Traditional lectures will be used, but there will also be "blended learning" methods which can include "flipped classroom" methods, where lecture material presented in a pre-recorded video is discussed in the classroom.

Students can seek advice and guidance while writing the 3-week project by attending the office hours that will be specifically scheduled once per week for this purpose by the lecturer/instructor
  • Category
  • Hours
  • Lectures
  • 24
  • Preparation
  • 96
  • Theory exercises
  • 12
  • Project work
  • 54
  • Exam
  • 20
  • Total
  • 206
Collective
Continuous feedback during the course of the semester
Credit
7,5 ECTS
Type of assessment
Continuous assessment
Type of assessment details
Continuous evaluation based on 1 problem set (assignment), and 1 (individual) written project.
Aid
All aids allowed
Marking scale
7-point grading scale
Censorship form
No external censorship
One internal examiner
Re-exam

25 min oral examination, no preparation time. During the exam, the student is allowed to consult a note the student has made, of length no longer than 1 A4 page per exam question/topic, briefly at the beginning after drawing an exam question. No other material may be used of consulted during the exam.

Criteria for exam assesment

The student should convincingly and accurately demonstrate the knowledge, skills and competences described under Learning Outcome.