MAU11602 Computation theory and logic
| Module Code | MAU11602 |
|---|---|
| Module Title | Computation theory and logic |
| Semester taught | Semester 2 |
| ECTS Credits | 5 |
| Module Lecturer | Prof. Colm Ó Dúnlaing |
| Module Prerequisites | N/A |
Assessment Details
- This module is examined in a 2-hour examination at the end of Semester 2.
- Continuous assessment contributes 30% towards the overall mark.
- Re-assessment, if needed, consists of 100% exam.
Contact Hours
11 weeks of teaching with 3 lectures per week.
Tutorials will be held during the lecture time slots and a revision will take place at the end of the semester.
Learning Outcomes
On successful completion of this module, students will be able to
- Construct simple Turing machine programs.
- Construct proofs of formulae in propositional and first-order logic, including resolution, the deduction theorem and derived rules.
- Define truth in a model, and distinguish between truth in a model and provability in a proof system.
- Determine the solvability or otherwise of various computational problems.
Module Content
- Turing machines, universal Turing machine, halting problem, recursion (fixpoint) theorem, recursive separability.
- Propositional logic, resolution, Mendelson's axioms I--III, deduction theorem, completeness.
- First-order theories with Mendelson's axioms I--V, interpretations and models, Gödel's completeness theorem.
- Peano arithmetic and, if time permits, representability of arithmetic functions and Gödel's incompleteness theorems.