This course introduces some classical models of computation, and it covers the fundamental notions, techniques, and results of computability theory.
Time and location
Class: Wednesday, 10-12 (c.t.), start on 02.11.
Exercise session: Wednesday 9-10 (c.t.), start on 09.11.
Classes take place via Zoom. Meeting details will be provided via LSF or email. If you have not received them by Thursday 29.10 please get in touch with me.
Prerequisites
Basic knowledge of first-order logic.
Assessment
Final exam: 10 Feb 2021, 9:30-12.
Re-sit exam: 03 Mar 2021, 9:30-12.
Details will be discussed in class.
Textbook
Cutland, Computability: an introduction to recursive function theory.
Course program (preliminary)
04 Nov. Introduction
Material: slides + Chapter 1.1-1.3 of the book.
Exercises: 1(a,b) on p. 21 + these
Part I: models of computation
11 Nov. Unlimited register machines
Material: Chapter 1.4 + 2.1-1.3
Exercises. Example solutions.
18 Nov. Recursive functions
Material: Chapter 2 and 3.2
Exercises. Example solutions.
25 Nov. Turing machines
Material: lecture notes
Exercises. Example solutions.
02 Dec. The Church-Turing thesis
Material: Chapter 3.7 of book + SEP article
Exercises: 1 and 2 on p. 71 of book. Example solutions.
Part II: introduction to computability theory
09 Dec. Coding programs as numbers.
Material: lecture notes on coding
Exercises
16 Dec. Diagonalization, halting problem, s-m-n theorem.
Material: Chapter 4.2-4.4 of book.
Exercises. Example solutions.
13 Jan. Universal programs, Kleene normal form, reduction between problems.
Material: class handout. Chapter 5 except for 5.2.2, Chapter 6 up to 6.1.5.
Exercises + example solutions.
20 Jan. Rice’s theorem, partial decidability.
Material: Chapter 6.1.6-6.1.7 and 6.6.1-6.6.6
Exercises. Example solution to the second one.
27 Jan. Recursive and recursively enumerable sets
Material: Chapter 6.6.11-6.6.13. Chapter 7 up to 7.2.9.
Exercises
03 Feb. Connections with arithmetic and Gödel’s theorem
Material: Chapter 7.2.13-7.2.16. Chapter 8. Class slides.
(Note: arithmetic will not be covered in the final exam.)
Practice exam. Example solutions.
10 Feb. Final exam.
Example solutions to some exam problems