Mathematics 114C, Computability Theory, Winter 2017, Log


L 28, March 17, F, Review.
L26, 27, March 13, 15, M, W. Chapter 5, the theorems of Tarski and Gödel.
L25, March 10, F. Will discuss Chapter 5 and go through Section 5A.
L24, March 8, W. Will finish Section 4F and discuss the material in Chapter 5 coming up next.
L22,23, March 3,6, F, M. Covered part of Section 4F and discussed the second midterm.
L21, March 1, W. Will cover Sections 4C and 4E.
L20, Feb 27, M. Will cover Section 4D.
L19, Feb 24, F. Will finish 4B and 4C and lead into the material in Section 4D.
L18, Feb 22, W. Will finish Section 4B, perhaps start on 4C. (Did not finish 4B.)
L17, Feb 17, F. Will start with Section 4B on r.e. sets and try to get to Myhill's Theorem 4B.8.
L16, Feb 15, W. Will cover Section 4A and start on 4B, going at least through Prop 4B.2. (Did not get to 4B.)
L15, Feb 13, M. I will outline the proof of Post's Theorem 3C.4 and (perhaps) also cover the little we will do with Turing machines in Section 3D.
L14, Feb 10, F. I went through 3B.6 and discussed briefly the proof of the "strong version" of the Normal Form Theorem in the remainder of Section 3B that we will not cover in detail.
L13, Feb 8, W. Will Start in Section 3B, aiming to get through 3B.6 and discuss the rest of the Section which we will not cover in detail.
L12, Feb 6, M. Covered Section 3A, on the Church-Turing Thesis.
L11, Feb 3, F. Finished Chapter 2.
L10, Feb 1, W. Will review and complete Section 2B and start discussing the basic Theorems 2C.2 (Soundness), 2C.4 (Transitivity) and 2C.5 (Least Fixed Points). (The aim is to finish Chapter 2 on Friday.)
L9, Jan 30, M. Covered most of the basic facts about recursive programs in Section 2B, including an introduction of the recursive machine associated with a partial algebra M and an M-program. E.
L8, Jan 27, F. Starting with (a review of) the semantics of T(M) in 2A.9, I will finish Section 2A and then move to Section 2B, aiming to get through the basic notions in 2B.1
L7, Jan 25, W. Will finish Section 2A; too many definitions, it will help if you can look at it before class.
L6, Jan 23, M. Finish Chapter 1 and start on Section 2A, aiming to get (close) to 2A.6.
L5, Jan 20, F. Start Section 1C and aim to go through most of it. (There are no difficult proofs in this section, but there are many definitions and it will help you follow the lecture if you read through p. 26 before class.)
L4, Jan 18, W. Finished Section 1B.
L3, Jan 13, F. Started on the theory of primitive recursive functions in Section 1B and got to the middle of Prop 1B.6.
L2, Jan 11, W. Finished Section 1A and got through the definition of Primitive Recursive Functions on N in Section 1B.
L1, Jan 9, M. After a few introductory remarks about the class, I started on the Notes and went (roughly) up to 1A.4 - which was left for the Section meeting.