Skip to main content

Trinity College Dublin, The University of Dublin

Trinity Menu Trinity Search

School of Mathematics

You are here Courses > Undergraduate > Courses & Modules

MAU11602: Introduction to Computation Theory and Logic

Credit weighting (ECTS)
5 credits
Semester/term taught
Hilary Term 2020-21
Contact Hours
11 weeks, including tutorials and a review period at the end of term.
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.
  • Propositional logic, resolution, Frege's axioms I--III, deduction theorem, completeness.
  • First-order theories, axioms IV, V models, completeness of first-order logic.
  • Peano Arithmetic, representability of arithmetic functions, Gü&del's incompleteness theorems.
Module Prerequisite
None beyond JF level modules.
Assessment Detail

(During the Covid-19 pandemic) Fortnightly quizzes and an assignment for 50%. Take-home final for 50%. Re-assessments if required will consist of 100% exam.