Skip to main content Skip to navigation

Module Catalogue

PH345-15 Computability Theory

Department
Philosophy
Level
Undergraduate Level 3
Module leader
Walter Dean
Credit value
15
Assessment
15% coursework, 85% exam
Study location
University of Warwick main campus, Coventry

Download as PDF

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, effectivity versus feasibility, relations to computational complexity theory, the P vs NP 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.
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.

Study time

Type Required
Lectures 9 sessions of 3 hours (87%)
Seminars 4 sessions of 1 hour (13%)
Total 31 hours

Private study description

No private study requirements defined for this module.

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 D2
Weighting Study time Eligible for self-certification
Assessment component
Assessed Exercises 15% No

An assessed exercises set.
Reassessment component is the same
Assessment component
In-person Examination 85% No

A 2-hour written exam.
Reassessment component is the same
Feedback on assessment

Exercise sets will be returned in conjunction with written feedback or posted solutions in line with the Philosophy department’s policies and guidance on giving feedback to students.

Past exam papers for PH345

Courses

This module is Core optional for:

  • Year 3 of UMAA-GV19 Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations

This module is Optional for:

  • Year 2 of UMAA-GV19 Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations
  • UPHA-VQ72 Undergraduate Philosophy and Literature
    • Year 2 of VQ72 Philosophy and Literature
    • Year 3 of VQ72 Philosophy and Literature
  • Year 2 of UPHA-V7ML Undergraduate Philosophy, Politics and Economics

This module is Core option list B for:

  • Year 4 of UMAA-GV19 Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations

This module is Option list A for:

  • Year 3 of UMAA-GV17 Undergraduate Mathematics and Philosophy
  • UMAA-GV19 Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations
    • Year 3 of GV19 Mathematics and Philosophy with Specialism in Logic and Foundations
    • Year 4 of GV19 Mathematics and Philosophy with Specialism in Logic and Foundations

This module is Option list B for:

  • Year 1 of TMAA-G1PE Master of Advanced Study in Mathematical Sciences
  • Year 2 of UMAA-GV17 Undergraduate Mathematics and Philosophy
  • Year 2 of UMAA-GV18 Undergraduate Mathematics and Philosophy with Intercalated Year
  • Year 4 of UPHA-VQ73 Undergraduate Philosophy and Literature with Intercalated Year

This module is Option list E for:

  • Year 2 of UPHA-V7MW Undergraduate Politics, Philosophy and Law