Computability 17/18

This course introduces some classical models of computation, and it covers the fundamental notions, techniques, and results of computability theory.


Announcements

The re-sit exam will be held in Room 021 on Monday 23/7, 10-12h.


Times and location

Class: Friday, 12-14, Room 021.
Exercise session: Wednesday, 11-12, Room 144.


Prerequisites

Basic knowledge of first-order logic.


Textbook

N. J. Cutland, Computability: an introduction to recursive function theory.


Course program (preliminary)

13-04 Introduction

Material: slides. Cutland, 1.1-1.2.

20-04 Unlimited register machines

Material: remainder of Chapter 1.
Exercises: 1(b,c,d,e) on pp. 21-22 + this exercise

27-04 Recursive functions

Material: Chapter 2 + 3.1-3.3
Exercises

04-05 Turing machines

Material: lecture notes
Exercises

11-05 Post systems

Material
Optional material 1; Optional material 2.
Exercises

18-05 The Church-Turing thesis, coding of programs

Material: slides + Sections 4.1-4.2
Practice examExample solutions.

25-05 Diagonalization, halting problem, s-m-n theorem, Kleene normal form

Material: Sections 4.3, 4.4, 5.1
Exercises

01-06 No class

Exercises

08-06 Universal program, Reduction between problems, Rice’s theorem

Material: Sections 5.2, 5.3, 6.1
Exercises

15-06 Partial decidability

Material: Section 6.6
Exercises (for Wednesday 27/6)

29-06 Recursive and recursively enumerable sets

Material: Sections 7.1, 7.2
Exercises

06-07 Connections with arithmetics and Gödel’s theorem

Material: slides

13-07 Final exam – Example solutions