PH345-15 Computability Theory
Introductory description
PH345-15 Computability Theory
Module aims
Computability theory is a subfield of contemporary logic which is also related to theoretical computer science and the foundations of mathematics. The goal of this module will be acquaint students with fundamental concepts and results in this field as illustrated by the following: models of computation (e.g. Turing machine, unlimited register machines, recursive functions), Church's Thesis, decidable versus undecidable problems, computable and computably enumerable sets, computational reductions (e.g. many-one and Turing reducibility), degree hierarchies, computational completeness, creative sets, Post's problem,
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.
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.
Study time
| Type | Required |
|---|---|
| Lectures | 9 sessions of 3 hours (18%) |
| Other activity | 9 hours (6%) |
| Private study | 114 hours (76%) |
| Total | 150 hours |
Private study description
Private study and preparation for classes.
Other activity description
Problem class
Costs
No further costs have been identified for this module.
You do not need to pass all assessment components to pass the module.
Students can register for this module without taking any assessment.
Assessment group B1
| Weighting | Study time | Eligible for self-certification | |
|---|---|---|---|
Assessment component |
|||
| Take-home examination | 100% | No | |
Reassessment component is the same |
|||
Feedback on assessment
Discussion and feedback on unassessed exercises during seminar.
Courses
This module is Optional for:
- Any PH programme
- Any PH programme