Content
This module is an introduction to logic, languages and computability. At first sight they may appear fairly disconnected but they are in fact all closely related.
The main topics covered are:
- Formal languages (regular, context free, etc.)
- Logic (propositional calculus, first order logic)
- Arithmetic, Gödel's and Tarski's theorems
- Sets (finite, countable, uncountable)
- Idealised machines (finite state automata, pushdown automata, Turing machines)
Text
There is no text for the module. I may provide lecture notes for some of the material. I will also post slides after the lectures.
| Monday | Tuesday | Wednesday | |
|---|---|---|---|
| Week 0 | Lecture 0 | Lecture 1 | Lecture 2 |
| Week 1 | Lecture 3 | Lecture 4 | Lecture 5 |
| Week 2 | Lecture 6 | Lecture 7 | Lecture 8 |
| Week 3 | Lecture 9 | Lecture 10 | Lecture 11 |
| Week 4 | Lecture 12 | Lecture 13 | Lecture 14 |
| Week 5 | Lecture 15 | Lecture 16 | Lecture 17 |
| Week 6 | Lecture 18 | Lecture 19 | Lecture 20 |
| Week 7 | Lecture 21 | Lecture 22 | Lecture 23 |
| Week 8 | Lecture 24 | Lecture 25 | Lecture 26 |
| Week 9 | Lecture 27 | Lecture 28 | Lecture 29 |
| Week 10 |
Exam
There will be single exam in the usual exam period, worth 70% of your module mark.
I have prepared a mock exam to help you in revising. The format of the exam is the same as the real exam and the type and level of difficulty should be similar but the topics mostly aren't. The module covers more topics than can be assessed in a two hour exam so any exam must make some sort of random selection of topics. The real exam and mock exam each have such a random selection but they are different random selections!
Assignments
There are weekly assignments for this module, worth 30% of your module mark.
They are due on Thursdays in lecture. Solutions will be posted a few days after they are due.
| Assignment | Due | Problems & Solutions |
|---|---|---|
| 0 | 29 January 2026 | problems solutions |
| 1 | 5 February 2026 | problems solutions |
| 2 | 12 February 2026 | problems solutions |
| 3 | 19 February 2026 | problems solutions |
| 4 | 26 February 2026 | problems solutions |
| 5 | 12 March 2026 | problems solutions |
| 6 | 19 March 2026 | problems solutions |
| 7 | 26 March 2026 | problems solutions |
| 8 | 2 April 2026 | problems |
Past versions of the module
Last year this module was taught by Nicholas Aidoo. I don't think there is a website for that version.
The year before it was taught by me. There is a webpage. The module has changed a fair amount since then so some material there may be helpful but some will not be.
Before that it was taught by Colm O'Dunlaing and I don't think there is a web page. The module has probably changed sufficiently since then that even past papers from that period are not useful.