Course Details in

Module Title	Computability and Logic
School	Mathematics
Department	Mathematics
Module Code	06 19609
Module Lead	BJ Philp
Level	Masters Level
Credits	20
Semester	Full Term
Pre-requisites	Foundation and Abstraction - (06 22512)
Co-requisites
Restrictions	Optional for All MSci programmes in Mathematics and MSci JH programmes including Mathematics
Contact Hours	Lecture-46 hours Tutorial-10 hours Total: 56 hours
Exclusions
Description	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. Logic is concerned with the consistency of sets of axioms, and setting up precise rules for deriving theorems from these axioms. Two significant theoroms (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 infiniate numbers. A familiarity with Level I Linear Algebra may be beneficial.
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 Explore these topics beyond the taught syllabus
Assessment	19609-01 : Assessments : Coursework (10%) 19609-03 : Exam : Exam (Centrally Timetabled) - Written Unseen (90%) 19609-04 : Extra Task (Sem 1) : Coursework (0%) 19609-05 : Extra Task (Sem 2) : Coursework (0%)
Assessment Methods & Exceptions	90% based on a 3 hour written examination in the Summer Term; 10% based on work during term-time.
Other
Reading List	Hoperoft, K. Introduction to Automata Theory. Cutland. Computability. Bodos, J. Computability and Logic.