Introduction to Computability 2020

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, 10-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

25 Nov. Turing machines

02 Dec. Post systems

09 Dec. The Church-Turing thesis, coding of programs


Part II: introduction to computability theory

16 Dec. Coding, diagonalization, halting problem.

23 Dec. s-m-n theorem, universal programs.

13 Jan. Kleene normal form, reduction between problems, Rice’s theorem

20 Jan. Partial decidability.

27 Jan. Recursive and recursively enumerable sets

03 Feb. Connections with arithmetic and Gödel’s theorem

 

10 Feb. Final exam.