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 | |||
| Week 3 | |||
| Week 4 | |||
| Week 5 | |||
| Week 6 | |||
| Week 7 | |||
| Week 8 | |||
| Week 9 | |||
| Week 10 |
Exams
There will be single exam in the usual exam period, worth 70% of your module mark.
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 | |
| 1 | 5 February 2026 | problems | |
| 2 | 12 February 2026 | ||
| 3 | 19 February 2026 | ||
| 4 | 26 February 2026 | ||
| 5 | 12 March 2026 | ||
| 6 | 19 March 2026 | ||
| 7 | 26 March 2026 | ||
| 8 | 2 April 2026 |
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.