Mastermath course Computability Theory, Fall 2014
Lecturers: Henk Barendregt and Sebastiaan Terwijn.
For information about the course also see the
Mastermath
webpage.
On this page we list the material treated so far.
(Lecturer indicated by HB or ST.)
We will be using the following syllabus
Computability Theory,
possibly extended with extra material.
Prerequisites for this course are a basic course in logic,
as well as the mathematical maturity required for a master's course in mathematics.
| Sept 08 ST. |
Sections 2.1 -- 2.3.
|
| Sept 15 ST. |
Section 2.4.
|
| Sept 22 ST. |
Sections 2.4, 3.1, 3.2.
|
| Sept 29. ST. |
Sections 3.3, 3.4.
|
| Oct 6 HB. |
Sections 3.5, 3.7. Beginning 4.1.
Slides:
The recursion theorem.
|
| Oct 13 ST. |
Section 3.6. Discussion of hyperimmune sets.
Here is a
handout about h-immune sets.
|
| Oct 20 HB. |
Section 4.1.
Slides:
Combinators and Lambda Calculus.
|
| Oct 27 HB. |
Sections 4.1, 4.2.
Slides:
Extra material Arithmetical Hierarchy.
The impact of the lambda calculus.
|
| Nov 3 ST. |
Sections 4.2, 5.1, 5.2.
|
| Nov 10 HB. |
Slides: Systematic Lambda Calculus.
Proof Church-Rosser theorem.
Quoting lambda terms.
|
| Nov 17 HB. |
Slides: Self-evaluation in lambda calculus.
|
| Nov 24 ST. |
Sections 5.2, 5.3, 5.4.
|
| Dec 1 HB. |
Slides: Theorems about typed lambda calculus.
Extra: Inhabitation algorithm.
|
| Dec 8 HB. |
No new material. Exercises!
|
| |
Exercises part HB
|
| Dec 15. |
Exam. Room 079, 10:00-13:00.
Here is a link to the
exam with answers.
|
| Jan 19. |
Retake. Room BBL 065, 14:00-17:00.
|
|