Computability, Turing Machines, and Gödel's Incompleteness Theorems
Course 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.
MSc Programme in Mathematics
MSc Programme in Mathematics with a minor subject
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.
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
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.
- ECTS
- 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 assessment
The student should convincingly and accurately demonstrate the knowledge, skills and competences described under Learning Outcome.
Single subject courses (day)
- Category
- Hours
- Lectures
- 24
- Preparation
- 96
- Theory exercises
- 12
- Project work
- 54
- Exam
- 20
- English
- 206
Kursusinformation
- Language
- English
- Course number
- NMAK24006U
- ECTS
- 7,5 ECTS
- Programme level
- Full Degree Master
- Duration
-
1 block
- Placement
- Block 1
- Schedulegroup
-
B
- Capacity
- No limitation – unless you register in the late-registration period (BSc and MSc) or as a credit or single subject student.
- Studyboard
- Study Board of Mathematics and Computer Science
Contracting department
- Department of Mathematical Sciences
Contracting faculty
- Faculty of Science
Course Coordinator
- Asger Dag Törnquist (6-67796d6b787a4673677a6e34717b346a71)
Are you BA- or KA-student?
Courseinformation of students