# Module MAU11602: Introduction to Computation Theory and Logic 5 credits

**Credit weighting (ECTS)**- 5 credits
**Semester/term taught**- Trinity Term 2019-20
**Contact Hours**-
11 weeks, including tutorials which will be held in lecture slots, and a review period at the end of term.

**Lecturer****Learning Outcomes**- On successful completion of this module students will be able to
- Construct very simple Turing machine programs.
- Construct proofs of formulae in propositional and first-order logic, including resolution, the Deduction Theorem, and derived rules.
- Determine the solvability or otherwise of various computational problems.
- Extend their knowledge of mathematical logic or proceed to further study of the subject.

**Module Content**-
- Turing machines, universal Turing machine, halting problem, recursion (fixpoint) theorem, recursive separability.
- Propositional logic, resolution, Frege's axioms I--III, deduction theorem, completeness.
- First-order theories, axioms IV, V models, skolem forms, Herband's Theorem, completeness of first-order logic.
- Peano Arithmetic, representability of arithmetic functions, Gödel's incompleteness theorems.

**Module Prerequisite**- None beyond SF level modules.
**Assessment Detail**-
2-hour examination counting for 80%. Fortnightly quizzes will count for 20%. .