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.

Homework assignments:

• Fourth homework assignment: download here. It is due on April 13.
• Third homework assignment is due on March 24. The homework consists of: 1) Exercises 4.1, 4.9, 4.12. 2) Let f(x)=2x, g(x)=x+1. Use the back-and-forth method as illustrated in class and in the notes to find h(6), where h is the bijection resulting from the argument. 3) Graduate students should also complete exercise 4.15.
• Second homework assignment is due on Feb. 10. The homework consists of: 1) All students should complete Exercise 2.2. 2) All students should choose 3 more exercises from the following list: Ex. 1.6, 1.7, 1.14, 2.4, 2.5. 3) Graduate students should also complete exercise 1.11 (note: this refers back to 1.10 which you may assume given).
• First homework assignment: download here. It is due on Jan. 23rd.
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):

• Nigel Cutland: Computability
• Hartley Rogers: Theory of Recursive Functions and Effective Computability
• Piergiorgio Odifreddi: Classical Recursion Theory, Vol.1
• Robert Soare: Recursively Enumerable Sets and Degrees

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.