First homework assignment (due date: Thursday Sept. 27th, 5pm): choose a selection from the exercises which satisfies the following requirements: 1) not just all exercises from one topic, but as many topics represented as possible; 2) total number of *s: 8 for undergraduate students, 12 for graduate students. 3) You don’t have to pick *** or **** level exercises, but try not to pick only the easiest exercises. In short, make a reasonable selection. If you wish to do some exercises from the book that’s fine too (then let me know which and I’ll rate them).
You’re encouraged to discuss problems amongst each other and with me (if you’re stuck or uncertain as to whether you’re doing the right thing) but all your answers should be clearly motivated and formulated in your own words.
Second homework assignment (due date: Thursday Oct. 11, 5pm): choose a selection from the exercises in chapter 2. Make sure to do at least one problem from each topic. For undergraduates, do at least 8*s. For graduate students, do at least 12*s.
Third homework assignment (due date: Thursday Oct. 25th, 5pm):
choose a selection from the exercises in chapter 3. Make sure to do at least one problem from each topic. For undergraduates, do at least 12*s. For graduate students, do at least 16*s. Note: don’t do the exercises which
appear in the book as Theorems 2.14, 2.15 in Ch 7.
Fourth homework assignment (due date: Monday Nov. 19th, 5pm):
choose a selection from the
exercises in chapter 4. Make sure to do at least one problem from each topic.
For undergraduates, do at least 12*s. For graduate students, do at least 16*s
Sept. 10th: Organizational meeting. Changed class times to Mon 4-5.30, Tue 2.30-4.
Sept. 11th.
Material covered: introduction to the subject; goals and strategies of recursion theory; connections of recursion theory with other areas of mathematics and computer science.
What to read: Introductory chapter in the notes. Some aspects of what we discussed are also touched upon in Cutland, e.g. in Chapter 6, sections 2-5.
Sept. 17th:
Material covered: primitive recursive functions – definition and examples; primitive recursive sets and Boolean combinations. Proofs as algorithms. Example of an algorithm which doesn’t give a PR function: Goodstein sequences.
What to read: In the notes, this material is covered in Chapter 1, up to 1.2.1. In Cutland, in Chapter 2, up to section 4.5. The Goodstein sequences are not in either and are not part of the official course/exam material, but the interested reader can find some more on Wikipedia.
Sept. 18th:
Material covered: more closure properties of the class PR: bounded quantifiers, minimalization, definition by cases. Codings of the plane, of finite sequences and of finite sets.
What to
read: 1.2.2-1.3.1 in the notes. The closure properties of PR are in
Sept. 24th:
Material covered: Diagonalization and arithmetization: coding of PR functions as numbers; proof that Eval is not PR; diagonal arguments in general. Ackermann’s function, double recursion.
What to read: In the notes: sections 1.3.2-1.4. In the book, section 4.3.
Sept. 25th:
Material covered: mu-operator, general recursive functions; closure properties; recursive sets; semi-recursive sets. Proof that Ackermann’s function is recursive.
What to read: In the notes: 1.4.1-1.4.4. In the book: Ch2. section 5, Ch3, sections 2,3.
Oct. 1st:
Material covered: Register machine programs; computations and computable functions; Macros.
What to read: In the notes: section 2.1. In the book, sections 1.1-1.3.
Oct. 2nd:
Material covered: Coding of programs; proof that computable=recursive. Normal form theorem.
What to read: In the notes: sections 2.2,2.3. In the book: Ch4.1-4.3
Oct. 9th:
Material covered: Enumeration and parametrization. Fixed point theorem and applications.
What to read: In the notes: sections 3.1-3.2. In the book: Ch4.4, 5.1.
Oct. 15th:
Material covered: Second recursion theorem and applications. Recursively enumerable sets. Proof that the Halting problem is not decidable. Characterization of r.e. sets.
What to read: In the notes: sections 3.2-3.3. In the book: Ch 6.1, 6.3, 6.6, 7.1, 7.2.
Oct. 16th:
Material covered: More on r.e. sets: lattice-theoretic aspects; undecidability results; pairs of inseparable r.e. sets; index sets; Rice’s theorem.
What to read: In the notes: sections 3.3-3.4. In the book: Ch7.1, 7.2 (but not the theorem by Rice-Shapiro).
Oct. 22st:
Material covered: Reducibility relations and degrees. Many-one reduction and 1-reduction. M-completeness.
Myhill’s isomorphism theorem.
What to read: In the notes: sections 4.1.1 and 4.1.2. In the book: Ch 9.1-9.3
Oct. 23rd:
Material covered: More examples of reductions; creative sets. Myhill’s theorem that creative=m-complete.
What
to read: In the notes: sections 4.1.3 and 4.1.4. In the book:
Oct. 29th:
Material covered: incomplete sets, Post’s construction of a simple set.
What to read: In the notes: section 4.2.
Oct. 30th:
Material covered: Movable marker construction of a simple set (priority argument). Relative computability and Turing reducibility.
What to read: In the notes: section 4.2, 4.3.
Nov. 5th:
Material covered: Jump operation, Jump hierarchy, Jump theorem.
What to read: In the notes: section 4.3.
Nov. 6th:
Material covered: Arithmetical hierarchy, Tarski-Kuratowski algorithm
What to read: In the notes: section 4.4.1, 4.4.2.
Nov. 12th:
Material covered: Classifications of unsolvable problems, structure of the hierarchy.
What to read: In the notes: section 4.4.
Nov. 13th:
Material covered: Post’s theorem and the Hierarchy theorem .
What to read: In the notes: section 4.4.
Nov. 20th:
Material covered: Peano arithmetic, representing functions and relations in PA, representation of PR functions.
What to read: Cutland chapter 8 treats this material lightly; rely on your notes taken in class!
Nov. 21st:
Material covered: Coding of syntax; diagonalisation lemma.
What to read: See above.