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
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:

Note: All of the homework assignments are due at the beginning of the lecture of that day.

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.