Introductory description

PH345-15 Computability Theory

Module aims

Outline syllabus

This is an indicative module outline only to give an indication of the sort of topics that may be covered. Actual sessions held may differ.

Week 1: Algorithms, and Unlimited Register Machines (URMs)
Week 2: Combining URMs, recursive functions
Week 3: Turing machines, Church’s Thesis
Week 4: Enumerating machines, the s-m-n Theorem, universality
Week 5: Diagonalization, undecidable problems
Week 7: Recursive and recursively enumerable sets
Week 8: Reducibilities, degrees, completeness
Week 9: Completeness (cont.), the Recursion Theorem
Week 10: Complexity theory and the P versus NP problem

Learning outcomes

By the end of the module, students should be able to:

• state and understand basic definitions and results about machine models, computational problems, undecidability, degree notions, and completeness.
• follow and construct mathematical proofs involving computability theoretic notions and to explain their significance in regard to foundational issues like undecidability and Church's Thesis.

Indicative reading list

Computability: an introduction to recursive function theory by N. Cutland, Cambridge, 1980.
Computability theory by Barry Cooper, Chapman & Hall, 2000.
Introduction to the theory of computation by M. Sipser, Thomson, 2013.
Computability and logic 5th ed. by G. Boolos, J. Burgess, and R. Jeffrey, Cambridge, 2007.
The Nature of Computation by C. Moore. and S. Mertens, Oxford, 2011.

Subject specific skills

students should have specific knowledge of the models of computation covered in the module, facility in constructing and manipulating their instances, and an ability to reason abstractly about their behaviour.

Transferable skills

apply and generalize from these notions in order to both concretely construct models of computation and to prove results about them.