Course Details in

Module Title	Computability and Logic
School	Mathematics
Department	Mathematics
Module Code	06 19603
Module Lead	BJ Philp
Level	Honours Level
Credits	20
Semester	Full Term
Pre-requisites	LC Algebra & Combinatorics 1 - (06 25659) LI Algebra & Combinatorics 1 - (06 27363)
Co-requisites
Restrictions	Optional for: All MSci programmes in Mathematics; BSc Mathematical Sciences; BSc Mathematical Sciences with Study in Continental Europe; All programmes including a Major in Mathematics; All JH programmes
Contact Hours	Lecture-46 hours Tutorial-10 hours Total: 56 hours
Exclusions
Description	Computability is concerned with the mathematics of computation on idealised 'computers', such as Turing machines. In particular, the module will study the following fundamental mathematical questions: (i) Which problems can be solved by a computer? (ii) Which problems can be solved efficiently by a computer? Question (ii) is actually still wide open, but a number of surprising results can be obtained. 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.
Learning Outcomes	By the end of the module the student should be able to: Analyse simple algorithms, determining relevant features such as their outputs, whether or not the algorithm halts, and if so what resources are required for this Write programs for the simple machine models studied in the course Demonstrate an understanding of some of the applications of the mathematical theory of these machines Construct formal proofs in the propositional and predicate calculus Understand the connections between semantic notions in logic and syntactic notions Apply the Soundness Theorem to demonstrate nonprovability of certain statements Apply the Completeness Theorem and/or Compactness Theorem to demonstrate the existence of 'new' mathematical structures
Assessment	19603-01 : Assessments : Coursework (10%) 19603-03 : Exam : Exam (Centrally Timetabled) - Written Unseen (90%)
Assessment Methods & Exceptions	Assessments: 19603-01: Exam : Exam (CT) - Written Unseen (90%) 19603-02 : Continuous Assessment : Coursework or class Tests (10%)
Other
Reading List	Hoperoft, K. Introduction to Automata Theory. Bodos, J. Computability and Logic. Cutland. Computability.