Mathematics course u11602, Hilary term 2022. Online notes.

1. Sources
2. Natural numbers and Turing machines
3. A C program which simulates Turing machines
4. Multitape Turing machines
5. Encoding Turing machines
6. The Halting Problem
7. A Universal Turing Machine
8. Truth-tables and Propositional Logic
9. Resolution
10. Axiom system for propositional logic
11. First-order languages and theories
12. Semantics of first-order theories
13. Snapshots and substituting $u$ free for $x_i$
14. Soundness of Predicate Calculus
15. Deduction Theorem for first-order logic
16. The `fix' rule.
17. Renaming bound variables, and other techniques
18. Completeness of first-order theories
19. Peano Arithmetic
20. Primitive recursive functions
21. Representability of primitive recursive functions
22. The semicomputable functions $\phi_m$ and the Fixed Point Theorem
23. Turing machines encoded, again
24. G\"odel, Tarski, Church
25. Integers can be infinite
26. Syllabus for 2022 exam