Department of Computer Science and Technology

Course pages 2021–22

# Computation Theory

Principal lecturer: Prof Andrew Pitts
Taken by: Part IB CST
Term: Lent
Hours: 12
Format: In-person lectures
Suggested hours of supervisions: 3
Prerequisites: Discrete Mathematics
This course is a prerequisite for: Complexity Theory, Quantum Computing, Types
Exam: Paper 6 Question 5, 6
Past exam questions, timetable

## Aims

The aim of this course is to introduce several apparently different formalisations of the informal notion of algorithm; to show that they are equivalent; and to use them to demonstrate that there are uncomputable functions and algorithmically undecidable problems.

## Lectures

• Introduction: algorithmically undecidable problems. Decision problems. The informal notion of algorithm, or effective procedure. Examples of algorithmically undecidable problems. [1 lecture]
• Register machines. Definition and examples; graphical notation. Register machine computable functions. Doing arithmetic with register machines. [1 lecture]
• Universal register machine. Natural number encoding of pairs and lists. Coding register machine programs as numbers. Specification and implementation of a universal register machine. [2 lectures]
• Undecidability of the halting problem. Statement and proof. Example of an uncomputable partial function. Decidable sets of numbers; examples of undecidable sets of numbers. [1 lecture]
• Turing machines. Informal description. Definition and examples. Turing computable functions. Equivalence of register machine computability and Turing computability. The Church-Turing Thesis. [2 lectures]
• Primitive and partial recursive functions. Definition and examples. Existence of a recursive, but not primitive recursive function. A partial function is partial recursive if and only if it is computable. [2 lectures]
• Lambda-Calculus. Alpha and beta conversion. Normalization. Encoding data. Writing recursive functions in the lambda-calculus. The relationship between computable functions and lambda-definable functions. [3 lectures]

## Objectives

At the end of the course students should

• be familiar with the register machine, Turing machine and lambda-calculus models of computability;
• understand the notion of coding programs as data, and of a universal machine;
• be able to use diagonalisation to prove the undecidability of the Halting Problem;
• understand the mathematical notion of partial recursive function and its relationship to computability.