Department of Mathematics
Homepages
(hier geht es zur ggf. vollständigeren Homepage im alten Layout)
(this way to the possibly more complete Homepage in the old layout)
Notes 1
Notes 2
Notes 3 and 4
Notes 5
Notes 6
Notes 7, 8 and 9
Notes 10
Notes 11
Notes 12
Notes 13
Notes 14
Exercises Number Theory
Notes 15
Notes 16
Notes 17
Notes 18
Notes 19
Notes 20
Notes 21
Notes 22
Here are my own Notes on Recursion Theory (latest update: 16 October)
And here is an extra set of notes on Gödel's Incompleteness Theorem (latest update: 17 December)
(this way to the possibly more complete Homepage in the old layout)
Recursion Theory
Fall 2007-2008
Here are the lecture notes by Piet Rodenburg:Notes 1
Notes 2
Notes 3 and 4
Notes 5
Notes 6
Notes 7, 8 and 9
Notes 10
Notes 11
Notes 12
Notes 13
Notes 14
Exercises Number Theory
Notes 15
Notes 16
Notes 17
Notes 18
Notes 19
Notes 20
Notes 21
Notes 22
Here are my own Notes on Recursion Theory (latest update: 16 October)
And here is an extra set of notes on Gödel's Incompleteness Theorem (latest update: 17 December)
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 |