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, K_{0}, 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 -&Sigma_{1} 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 W_{e,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, K_{0} and K_{1} 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 Φ_{e}^{A}(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 |