The slides for lectures 16 -- are now posted
here.
L19, Feb 22, F. Will finish Chapter 4.
This class is cancelled
L18, Feb 20, W. After a few remarks on Turing
reducibility, I will move to--and try to cover in full---Post's
results on productive, creative and simple sets and (perhaps) get
started on the 2nd Recursion theorem in Section 4D.
L17, Feb 15, F. Will start with the proof that K is complete
(Proposition 4B.7) and then spend most of the hour proving Myhill's Theorem,
Theorem 4B.8. (Read ahead if it is possible: the proof of Myhill's Theoerm
is not trivial.)
L16, Feb 13, W. Start on 4B and aim to get to Myhill's
Theorem 4B.8 and (at least) motivate it.
L15, Feb 11, M. Will cover Section 4A and start on 4B. (Did
not get into 4B.)
L14, Feb 8, F. Will explain and discuss briefly the
Church-Turing Thesis in Section 3B, and then make some remarks on
the remainder of Chapter 3 which we will not cover carefully now.
The main aim is to get started on Chapter 4 on Monday.
L13, Feb 6, W. Will finish Section 3A (one way or the
other) and start on the Church-Turing Thesis in Section 3B.
L12, Feb 4, M. Will try to cover Section 3A, skipping
details. (Reading ahead will really help this time.)
L11, Feb 1, F. Went over the midterm and started on
Section 3A.
L10, Jan 30, W. Will prove Corollary 2C.4 and use it to
prove the closure properties of the set of recursive partial
functions on a partial algebra without appealing directly to
their characterization in terms of least-fixed-points. Will also
review and discuss what will be covered in the midterm.
L9, Jan 28, M. Will finish Section 2B, mostly explaining by examples
how the recursive machine works. Hope to start discussing the
results in Section 2C, especially Lemma 2C.1 and the basic Soundness Theorem
2C.2.
L8, Jan 25, F. Will (try to) cover Section 2B; read it ahead
of class if possible.
L7, Jan 23, W. Will start on Section 2B and try to reach
(at least) the definition of the recursive machine.
L6, Jan 18, F. Will start on Chapter 2 and aim to finish
Section 2A; no difficult proofs, but many definitions---try to read
the section before the class.
L5, Jan 16, W. Will finish Chapter 1, putting emphasis on
understanding how we deal with partial functions and recursive
equations. It is very much worth reading Section 1C, especially
the proof of Proposition 1C.8 which involves many new ideas.
L4, Jan 14, M. Go quickly over sequence codings (1B.12)
and then move to Section 1C and try to finish it.
L3, Jan 11, F. Start with 1B.3 and aim to finish Section
1B, the elementary theory of primitive recursive functions.
L2, Jan 9, W. Review briefly, go over the basic facts
about the Ackermann function and then aim to reach and cover part
of Proposition 1B.3.
L1, Jan 7, M. After a few introductory remarks about the
class, I will start on the Notes and aim to go through 1A.5,
leaving the detailed proof of 1A.4 for the Section meeting on
Thursday.