I gave these lectures at the Department of Computer Science of the University of Bath. (The “.ps.gz” files can be viewed with “ghostview”, “gv”, or any other Postscript viewer.)
CM10020: Computability and decidability (Semester 2 of 2004)
- Handout 1 (Introduction, Sets & Enumerability) pdf / ps.gz / 4 on 1 page ps.gz
- Handout 2 (Enumerability & diagonalization) pdf / ps.gz / 4 on 1 page ps.gz
- Handout 3 (Automata) pdf / ps.gz / 4 on 1 page ps.gz
- Handout 4 (Non-deterministic finite automata) pdf / ps.gz / 4 on 1 page ps.gz
- Handout 5 (NFA’s & regular languages) pdf / ps.gz / 4 on 1 page ps.gz
- Handout 6 (Regular languages continued & Formal grammars) pdf / ps.gz / 4 on 1 page ps.gz
- Handout 7 (Context-free grammars) pdf / ps.gz / 4 on 1 page ps.gz
- Handout 8 (Limits of computability & Turing Machines) pdf / ps.gz / 4 on 1 page ps.gz
- Handout 9 (Uncomputability (for Turing machines)) pdf / ps.gz / 4 on 1 page ps.gz
- Proofs that the diagonal function, the self-halting function, and the halting function are not Turing-computable: pdf / ps.gz / 4 on 1 page ps.gz
- Handout 10 (Abacus machines) pdf / ps.gz / 4 on 1 page ps.gz
- Handout 11 (Recursive functions – Part 1: primitive recursion) pdf / ps.gz / 4 on 1 page ps.gz
- Handout 12 (Recursive functions – Part 2: primitive recursion (second part) & minimization) pdf / ps.gz / 4 on 1 page ps.gz
- Handout 13 (Recursive relations – Part 1) pdf / ps.gz / 4 on 1 page ps.gz
- Handout 14 (Recursive relations – Part 2) pdf / ps.gz / 4 on 1 page ps.gz
- Handout 15 (Closing the circle) pdf / ps.gz / 4 on 1 page ps.gz
- Handout 16 (Universal Turing Machine, semi-recursive relations) pdf / ps.gz / 4 on 1 page ps.gz
- Handout 17 (Revision) pdf / ps.gz / 4 on 1 page ps.gz
- Handout 18 (Revision Part 2) pdf / ps.gz / 4 on 1 page ps.gz
CM30071: Logic and its applications (Semester 2 of 2004)
- Introduction pdf / ps.gz
- Propositional logic (revision) & semantic entailment pdf / ps.gz
- Handout 1, containing both sets of slides above ps.gz
- Handout 2, Natural deduction pdf / ps.gz
- Handout 3, Soundness & Completeness pdf / ps.gz
- Handout 4, Completeness & Predicate Logic ps.gz
- Handout 5, Natural deduction for predicate logic ps.gz
- Handout 6, Natural deduction for predicate logic ps.gz
- Handout 7, Hoare logic ps.gz
- Handout 8, Hoare logic (part 2) ps.gz / pdf
- Handout 9, Sequent calculus ps.gz / pdf
- Handout 10, Sequent calculus vs. natural deduction ps.gz / pdf
- Handout 11, Sequent calculus, proof search & logic programming ps.gz / pdf
- Handout 12, Sequent calculus, proof search & logic programming (addendum). Preview of modal logic. ps.gz / pdf
- Handout 13, Modal logic ps.gz / pdf
- Handout 14, Natural deduction for modal logic ps.gz / pdf
- Handout 15, Intuitionistic logic (part 1/2) ps.gz / pdf
- Handout 16, Intuitionistic logic (part 2/2) ps.gz / pdf
- Handout 17, Lambda-calculus & Propositions-as-Types ps.gz / pdf
- Handout 18, Revision ps.gz / pdf