Computability and Logic

School of Mathematics

College of Engineering and Physical Sciences


Code 19603

Level of study Third/Final year

Credit value 20

Semester Students may study either 1, 2 or both.

Pre-requisite modules 22481

Module description

Semester 1: Computability is concerned with the mathematics of computation on idealised 'machines', such as Turing machines, register machines etc. These machine models are mathematical objects, and as such are the subject of an important mathematical theory which has many practical applications, and applications to many areas of pure mathematics, as well as applications to computer science. In this module, one of these machine models will be taken and studied in depth, and the theory will be developed far enough for the student to appreciate some of the wide range of applications available.

Semester 2: Logic is concerned with the consistency of sets of axioms, and setting up precise rules for deriving theorems from these axioms. Two significant theorems (the Soundness Theorem and the Completeness Theorem) will be proved. The Soundness and Completeness Theorems have important applications for mathematics. In one direction, they are applied to give rigorous proofs that certain statements cannot be proved from given axioms. In the other direction, they are applied to provide new interesting mathematical structures such as 'non-standard' versions of the integers which behave like the usual finite integers in many ways but which nevertheless contain infinite numbers. A familiarity with Level I Linear Algebra may be beneficial.

Teaching and learning methods