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
pp 20-24   Homework 3 (due Thursday 20th)  
Monday 17 September -More on reductions and degrees
-Least upper bound, greatest lower bound
-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 ⇒ Δ01
-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
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)
-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