NEWS: Next Thursday 13 December is the final deadline for any homework that you may still wish to submit and get credits for.
| Date | Material covered | Syllabus | Homework |
| Monday 3 September |
-Introduction: algorithms -Diagonalization problem -Primitive recursion |
pp 1-7 | Homework 1 (due Monday 10th) |
| Thursday 6 September |
-Ackermann function -General recursive and μ-recursive functions -Turing machines -Church-Turing thesis |
pp 8-16 | Homework 2 (due Thursday 13th) |
| Monday 10 September |
-Gödel Numbering -Coding Turing machines -Padding Lemma -Kleene's Normal Form Theorem |
pp 17-19 | |
| Thursday 13 September |
-Another way of coding pairs as numbers -Enumeration Theorem -S-m-n Theorem -Computably enumerable (c.e.) sets -Uncomputable sets (K, K0, Halting problem) -Many-one reducibility, one-one reducibility -m-degrees |
pp 20-24 | Homework 3 (due Thursday 20th) |
| Monday 17 September |
-More on reductions and degrees -Least upper bound, greatest lower bound -Lattices -Index sets -Index set theorem |
pp 24-26 | Homework 4 (due Monday 24th) |
| Thursday 20 September |
-Computable permutations and isomorphisms -Myhill Isomorphism Theorem -Acceptable Numbering Conditions -Acceptable Numbering Theorem -&Sigma1 Normal Form -Quantifier Contraction Theorem |
pp 28-34 | Homework 5 (due Thursday 27th) |
| Monday 24 September |
-More on projections -Projections of c.e. sets -Functions as relations (graphs) -Graph theorem -Uniformization theorem, selector function |
pp 34-36 | |
| Thursday 27 September |
-Listing Theorem -Union Theorem, Intersection Theorem -Reduction principle for c.e. sets -Π1, Δ1 sets -Complementation theorem |
pp 36-38 | Homework 6 (due Thursday 4th) |
| Monday 1 October |
-Static and dynamic properties of c.e. sets -Uniformly c.e. (u.c.e.) sequences -Simultaneous computable enumerations (s.c.e.) -Dynamic definitions for c.e. sets |
pp 39-40 | |
| Thursday 4 October |
-Differences between "new" and "old" definitions of We,s -Dynamic Flow Theorem -Friedberg's Splitting Theorem |
pp 40-42 | Homework 7 (due Thursday 11th) |
| Monday 8 October |
-Fixed points -Recursion Theorem (Fixed Point Theorem) -Applications of Recursion Theorem |
pp 43-47 | |
| Thursday 11 October |
-Recursion Theorem with parameters -Different kinds of indices (Σ1, Δ0 and Δ1) -No effective procedure: Σ1 ⇒ Δ0/Δ1 -Canonical indices for finite sets -More on acceptable numberings |
pp 47-53 | Homework 8 (due Thursday 18th) |
| Monday 15 October |
-Rogers' Acceptable Numbering Theorem (finished) |
pp 52-53 | |
| Thursday 18 October |
PRACTICE SESSION: -practise exercises of section 1.5, or -do whatever there is demand for |
||
| Monday 22 October |
AUTUMN BREAK |
||
| Thursday 25 October |
AUTUMN BREAK |
||
| Monday 29 October |
-Some philosophy of mathematics -Hilbert's programme -Representability |
Notes 13 | |
| Thursday 1 November |
-More on representability -Lemma 40.2 (i), (ii) -Representability of monus -Representable relations vs. characteristic functions |
Notes 14 | Homework 9 (due Monday 12th) |
| Monday 5 November |
-More on representability -Representability closed under minimalization |
Notes 14 | Homework 10 (due Monday 12th) |
| Thursday 8 November |
LECTURE CANCELLED due to A Day of Mathematical Logic. |
||
| Monday 12 November | -The β-function | Notes 15 | |
| Thursday 15 November | -Total computable functions are representable -Coding syntax of logic -Church's Theorem -Gödel's First Incompleteness Theorem | Notes 16 | Homework 11 (due Thursday 22nd) |
| Monday 19 November |
-Complete sets (1-complete, r-complete) -Repeating: K, K0 and K1 are 1-complete -Productive and creative sets |
pp 55-56 | Homework 12 (due Monday 26th) |
| Thursday 22 November |
-More on productive and creative sets -Creative Set Theorem (Myhill) -Corollaries -Exercise 2.6.10 | pp 56-58 | Homework 13 (due Thursday 29th) |
| Monday 26 November |
-Oracle Turing Machines -Coding configurations, computations etc. |
pp 61-62 | Homework 14 (due Monday 3rd Dec.) |
| Thursday 29 November |
-Turing computable functions -Use functions -Computable approximations to ΦeA(x) -Master Enumeration Theorem -Use Principle -Standard theorems relativized to A -Turing degrees | pp 62-69 | Homework 15 (due Thursday 6th Dec.) |
| Monday 3 December |
-The Jump operator -Jump theorem (i)-(v) |
pp 69-70 | |
| Thursday 6 December |
-Jump theorem (v)-(vii) -Infinite hierarchy (0 < 0' < 0'' < ...) -Arithmetical hierarchy -Quantifier manipulation -Placing an index set in Σn or Πn |
pp 70-71 pp 89-93 |
Homework 16 (due Thursday 13th) |
| Monday 10 December |
-Post's Theorem -Hierarchy Theorem |
pp 94-95 | |
| Thursday 13 December |
PRACTICE SESSION |
| Tuesday 18 December: | EXAM RECURSION THEORY | 09.00 - 12.00 in A.303 |