# Module MA3463: Computation theory and logic I

Credit weighting (ECTS)
5 credits
Semester/term taught
Michaelmas term 2016-17
Contact Hours
10 weeks, 3 lectures including tutorials per week

Lecturer
Prof. Colm Ó Dúnlaing
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, (total) recursive functions are not even semidecidable.
• 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 first incompleteness theorem, Tarksi, and Church, as regards computability. Gödel's Theorem, original version.
• Consistency: Hilbert-Bernays derivability conditions I--III, deduction of Goedel's second incompleteness theorem. Another view: consistency related to recursiveness.
Module Prerequisite
None beyond SF level modules.
Assessment Detail
This module will be examined in a 2-hour examination in Trinity term. Fortnightly written assignments will count 10%, and 90% for the final. Supplementals are normally not available in this module (except in the case of JS TSM pattern A students).