Lectures by Carsten Führmann

I gave the two courses below at the Department of Computer Science of the University of Bath in Semester 2 of 2004.

Click on any lecture for a PDF.

CM10020: Computability and decidability

1. Introduction, Sets & Enumerability

2. Enumerability & diagonalization

3. Automata

4. Non-deterministic finite automata

5. NFAs & regular languages

6. Regular languages continued & Formal grammars

7. Context-free grammars

8. Limits of computability & Turing Machines

9. Uncomputability (for Turing machines)

9a. Proofs that the diagonal function, the self-halting function, and the halting function are not Turing-computable

10. Abacus machines

11. Recursive functions – Part 1: primitive recursion

12. Recursive functions – Part 2: primitive recursion (second part) & minimization

13. Recursive relations – Part 1

14. Recursive relations – Part 2

15. Closing the circle

16. Universal Turing Machine, semi-recursive relations

17. Revision

18. Revision Part 2

1a. Introduction

1b. Propositional logic (revision) & semantic entailment

2. Natural deduction

3. Soundness & Completeness

4. Completeness & Predicate Logic

5. Natural deduction for predicate logic

6. Natural deduction for predicate logic

7. Hoare logic

8. Hoare logic (part 2)

9. Sequent calculus

10. Sequent calculus vs. natural deduction

11. Sequent calculus, proof search & logic programming

12. Sequent calculus, proof search & logic programming (addendum). Preview of modal logic

13. Modal logic

14. Natural deduction for modal logic

15. Intuitionistic logic (part 1)

16. Intuitionistic logic (part 2)

17. Lambda-calculus & Propositions-as-Types

18. Revision