MAT4199 Winter 2015 |
Topics in Logic: Computability Theory |
Instructor | Pieter Hofstra |
Department of Mathematics and Statistics | |
Office 307G, 585 King Edward Avenue | |
(613) 562-5800, ext. 3494 | |
e-mail: phofstra@uottawa.ca | |
Office Hours | Tuesdays 10-12 or by appointment. |
Course Outline | Click Here. Please take your time to read through the course outline carefully, as it contains important information about the marking scheme, tests and assignments. |
Quick study guide: click here
Old final exam: click here
Midterm solutions: click here
Homework assignments:
Big numbers: Here is a discussion of very big numbers, fast growing functions and related matters.
Literature: Complete course notes are available here. Additional recommended reading (in order of difficulty):
Classes: Tuesdays 8:30-10:00 and Fridays 10:00-11:30, KEDB004. During the lectures, I will explain the material and illustrate with examples. Take detailed notes! Feel free to ask questions before, during or after class.
Lecture | Topics | To Read | |
Jan. 13 | Introduction to the course: informal discussion of computable and computably enumerable sets, Diophantine sets. | Introduction of the course notes. | |
Jan. 16 | Primitive recursion, primitive recursive functions. | Sections 1.1, and 1.3.1 in the notes. | |
Jan. 20 | Closure properties of PR functions and relations. Coding of PR functions, and the diagonal argument. | Section 1.3. in the notes. | |
Jan. 23 | Ackermann's function. General recursive functions. | Sections 1.3, and 1.4.1, 1.4.2 in the notes. | |
Jan. 27 | Register machines: programs, states, computations. Computable functions | Section 2.1. | |
Jan. 30 | Recursive = register machine computable. | Section 2.2. | |
Feb. 3 | Encoding of register machines and computations. Busy beaver functions. | Section 2.3 and 2.4. | |
Feb. 6 | Universality Theorem, Enumeration Theorem. Cartesian closure and the S-m-n-Theorem. | Section 3.1 (not 3.1.3) | |
Feb. 10 | Recursion theorems and applications. | Section 3.2 | |
Feb. 13 | Halting problem, recursively enumerable sets, Rice's Theorem. | Section 3.3. | |
Feb. 24 | Lattice-theoretic properties of r.e. sets. Reducibility relations. | Section 3.3. Section 4.1 | |
Feb. 27 | m-reducibility, m-completeness, creativity, 1-reducibility and recursive isomorphism types. | Section 4.1. | |
Mar. 6 | Myhill's isomorphism Theorem. Simple sets, Post's problem, random numbers. | Section 4.1. | |
Mar. 10 | Priority method for constructing simple sets | Section 4.2. | |
Mar. 13 | Turing degrees; jump operation, Jump theorem | Section 4.3. | |
Mar. 17 | More about the Turing degrees. Connections with arithmetic. | Section 4.3. | |
Mar. 20 | Introduction to the arithmetical hierarchy; Tarski-Kuratowski algorithm. | Section 4.4. | |
Mar. 24 | Hierarchy theorem and some exact classifications. | Section 4.4. | |
Mar. 27 | Peano Arithmetic and introduction to Incompleteness. | The following notes are useful: Notes on Peano Arithmetic . | |
Mar. 31 | Representation of primitive recursive functions in PA. Godel's beta-function. | Same as before. | |
April 7 | Recursive and r.e. sets in PA. Mini-incompleteness. | Same as before. | |
April 10 | Coding of syntax and proofs; diagonalization lemma. First and Second incompleteness Theorems. | Same as before. | |
April 14 | Applications of Incompleteness: ZFC, Lob's Theorem. Tarski's Theorem. Goodstein sequences. | Same as before. |