Mathematics 114C, Computability Theory, Winter 2019, Log


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.