Recursion Theory

More postings will follow on this page. We shall work with the book Computability Theory by S. Barry Cooper. I have bargained a significant discount at the Atheaneum bookstore . They will sell the book for 38.28. At Scheltema you will pay more than 50 Euro.


The course is tought by Joost J. Joosten and the Teaching Assistant is Daisuke Ikegami. Daisuke's email address is "ikegami "at" science "dot" uva "dot" nl". Below is a tentative schedule that shall almost surely be changed. According to the current schedule there are lectures on tuesdays and on wednesdays.

Examination


Exam preparation

We have covered all the material from the book up to and including the proof of Post's Theorem, Theorem 10.5.8. All this will be tested in the final exam. In the exam you can be asked to reproduce a condensed verion of the proof of one of the following four theorems:

Lemma 10.5.5;
Theorem 7.3.5;
Theorem 7.1.11;
Theorem 4.4.1





The final grade will consist of three parts.

First, there are the homework assignments. They constitute 30 % of the grade. The home work will be made public on this website right after the problem session on wednesday. It should be handed in (in printed or written form) to Daisuke before the next tuesday, so, at latest on monday, before 20:00 in his pigeon hole or before 24:00 by mail. You can either hand it in to him in person at Room P-120 or by depositing it in his mail box which you can find at the ground floor of the Euclides building. (Note that the mailbox of Daisuke is tagged I. Ikegami.) You will get your graded homework on the next problem session on wednesday. It is allowed to work together on a homework assignment. In this case, each student does hand in his or her own version mentioning with whom was collaborated.

Second, there is a midterm exam in Week 8 (that is, on tuesday October 24) which constitutes another 30 % of the final grade.

And finally, there is a final exam in Week 15 which constitutes the remaining 40 % of the grade.

Grading will be done on a scale from 0 to 10, rounding up at half points.


Here is a list of misprints. If you find a misprint that is not on the list yet, please let us know.

Week 1 (4-9 to 8-9)

Daisuke will tell at the end of his lecture on Wednesday what the homework exercises of Week 1 will be. If you cannot be present this wednesday, please ask one of your collegue students for the homework. Alternatively, you can write an email to Daisuke and he will send you the exercises. From the next week on, the homework will be announced on this webpage. The homework for the first week is 2.1.9; 2.2.3; 2.3.4; 2.3.5 and 2.4.8.

Week 2


And here are the slides of this week. Please, hand in the homework next week on time. The homework for this week consists of 2.2.13 (change "recursive" into "primitive recursive"), 2.1.14, 2.2.11, 2.2.19, and 2.2.21. HAND THEM IN ON TIME!!!!

Week 3

This weeks homework consists of 2.2.20, 2.2.22, from the book, and 7, and 8 from the extra exercises.

This week the homework has to be handed in in Joost's Pigeon's hole. PLEASE DO NOT SUBMIT ONLY BY EMAIL. HAND IN A PAPER COPY TOO.

Here are the slides of this week. In this week, we spoke about the essentiality of defining the recursive functions via the non-total ones. You can find this argument in a nice reader written by S. Terwijn. It is at the beginning of Section 2.2.2.



After the work-group, Daisuke and Joost agreed that the homework exercise 2.2.11 does not need to be done inside a formal system. Students that have lost points due to an earlier standard can go back with there homework to Daisuke and he will correct it.

Week 4

This weeks homework consists of
Exercise 2.3.7 (has to be annotated, a flowchart is also accepted) (L. L. Wortel has to make 2.2.16 and 2.2.20 instead)
Exercise 2.4.13
Exercise 3.1.20
Exercise 3.2.9 (very easy)
It has to be handed in again to Daisuke.

Currently, there is a thread on the FOM (Foundations of Mathematics) mailinglist on the history of the primitive recursive functions. The first message is here and you can also organize by threads .

Here are this week's slides. So, we have now finised Chapter 3 of the book.

Week 5 (2-10 to 6-10)

Here are this week's slides. So, we have now almost finised Chapter 4 of the book.
This week's homework consists of three exercises:

(1) Give a full proof, using the fixed point theorem that there exists a program that halts only on its own code and loops on all other inputs. (Hint: consult the slides)

(2) Exercise 4.2.7

(2) Exercise 4.5.1

Week 6

The homework for this week consists of 5.1.10, 5.2.11, 5.2.12, 5.2.15. Here are this week's slides.

Week 7

Here are this week's slides. We have now finished Chapter 5. A practice midterm exam will is published here. The homework consists of making the practice midterm exam.
DIFFERENT DEADLINE !!!!!!!!!!!!!!!!!!!!
The homework should be handed in, either by this friday before 20:00 in Daisuke's mail box, or before saturday 23:59 by email. Daisuke will return the corrected exams to you by leaving them on monday around 10:00 in his mail box. You can get them out there yourself. Daisuke has used the best five exercises from the homework to calculate your mark on it. So, the exercise that you made worst of the exam was not taken into account.

Week 8

There will be no lecture from 11:00-13:00. Instead we will have the midterm exam, tuesday October 24, 13.30-16.30, OMHP-C017 (OudeManHuisPoort 4-6). We shall have our workgroup on wednesday as normal.

The exam is NOT AN OPEN BOOK EXAM!!!!

Week 9 (30-10 to 3-11)

The midterm exam was done by 13 students, 10 of whom passed. After deleting one mark of a PhD student (8.4) the list becomes:
0101052 3.8
0306053 5.5
0323055 7.7
0477672 6.2
0610925 8.7
0627313 9.0
0642576 4.6
0642592 8.7
0642800 8.0
0642851 7.7
5699959 8.7
????? 5.1


Here are this week's slides. We have now more or less finished Chapter 6.

Exercise 6.2.7 (via a direct argument, i.e. without using Ex. 6.2.8, or its generalization as proved in class), 6.2.9, and 6.2.10 : homework. Note that 6.2.9 is pretty hard. Daisuke and Joost could not find a solution at first. Finally they have some solution. However, it is done by slightly altering the definitions of W_{e,s} ans A_s (alternatively one could reconsider the definition of \searrow). It is pretty natural to consider alternative definitions of the A_s. The only important features are that for each natural number s, the A_s is a decidable, or actually, finite set, and that the union of all the A_s equals A. Of course one can consider various definitions that satisfy these properties. One example would be to define A_s to be the set of {f(0), ..., f(s)} where f is a computable function whose range is A. If you are still stuck with the exercise, it can be good to look for hints in the existing literature. Note that below there are some relevant remarks in the question and answer session.

Week 10

I hereby announce that there will be an excellent talk next tuesday from 16:00-17:00 by Sebastiaan Terwijn. The exact location is P327. Please reserve this time-slot already in your planner. I expect to see you all there.

Here are this week's slides.

Daisuke has made a file containing two answers to Exercise 6.2.9. You are encouraged to read them both.

The homework will consist of 7.1.8, 7.1.12, 7.2.6, 7.2.13 and 7.2.18. As you see, many exercises involve notions from Section 7.2. Next week I will skip section 7.2, and trust that you have read and studied it.

Week 11

Here are this week's slides. We have now fully covered all the material from Chapter 7. The homework for this week consists of: 6.2.11, 7.2.14, 7.2.19, writing down CASE 2 from the proof of Rice's Theorem.

Other than the written homework, you are requireed to prepare a presentation of the proof of Theorem 7.3.5, including first an exposition of the idea's that are incorporated in the proof and next giving the detailed proof. Next lecture, one student will at random be chosen to give the presentation at the beginning of the lecture. The presentation should not exceed 6 minutes. This is very little time, so you are asked to present the proof in a very precise way. I think that the proof idea is more important than filling in the details.

On tuesday, 16:00-17:00 talk by Sebastiaan Terwijn. The exact location is P327. Please reserve this time-slot already in your planner. I expect to see you all there.

Title: Intervals in the Medvedev lattice.

Abstract: The Medvedev lattice is a structure from computability theory with ties to constructive logic. We will briefly describe this connection and the relation to structures such as the Turing degrees. We will then discuss structural properties of the Medvedev lattice, in particular, the size of its intervals. We prove that every interval in the lattice is either finite, in which case it is isomorphic to a finite Boolean algebra, or contains an antichain of size 22^\aleph_0, the size of the lattice itself. We also prove that it is consistent that the lattice has chains of this size, and in fact that these big chains occur in every interval that has a big antichain. We also study embeddings of lattices and algebras. We show that large Boolean algebras can be embedded into the Medvedev lattice as upper semilattices, but that a Boolean algebra can be embedded as a lattice only if it is countable. Finally we discuss which of these results hold for the closely related Muchnik lattice.

Week 12

I have found a nice reader by Avigad that might be good to read too. (A local version is here .)

This week's homework:
8.1.12,
8.1.13,
8.2.4,
9.3.2, and
9.3.3.

In class we worked on 9.2.13.

Here are this week's slides.

Week 13 (27-11 to 1-12)

Here are this week's slides. The homework for this week constists of Proving Remark 10.4.2 and making exercises 10.4.8, 10.4.9, 10.4.10, and 10.4.12. You will have to read some new theory(not more than two pages) to make these exercises.

Week 14

Final lecture. We have covered all the material from the book up to and including the proof of Post's Theorem, Theorem 10.5.8. All this will be tested in the final exam.

Here are this week's slides.

(Contrary to announced earlier...) The DEADLINE FOR THIS WEEK'S HOMEWORK WILL as always BE NEXT MONDAY, I.E., MONDAY DECEMBER 11!!!!!!!! The homework consists of Exercises 10.5.3 and 10.5.11 from the book and Exercises 4 and 5 from the practice exam.

Week 15

On tuesday, there is no lecture. On wednesday December 13, from 13:00 SHARP till 14:00 we will have an additional question hour. In particular, we shall discuss the answers to the practice exam. As always, we will reside in P018.

Week 16

On monday December 18 we will have the final exam from 9:30-12:30 in P017. It is NOT an open-book exam. The final exam will be put opnline later. Here are the final grades. For the homework, we took the best 11 out of 14 for each student.

Questions and answers

Question

I was wondering if you could explain what you mean in Problem 8(c) of the "Extra Exercise" (Week 3) sheet by "in some free-style algorithmic way." Also, what exactly are we supposed to describe this way? An enumeration procedure or something else?

Answer

The idea is that you have to describe the way the coding exposed in this exercise works. So, which pair gets associated with 0, which pair with 1, whihc pair with 2, etc. Once you have understood this pattern and properly described it, you can then actually prove that indeed the algorithm for enumerating the pairs can be summarized by the formula given in the exercise.

Question

Problem 7(a) (of the Extra Homework Week 3), as far as I can tell, is the same as Example 2.2.4 in the textbook. Should we skip this on the homework, or am I missing something?

Answer

Goos observation. You can just refer to this example in your answer.

Question

Ik snap niet precies wat er met 2^N wordt bedoelt. Is dat gewoon de naam voor de set of all subsets of N (dit is dan toch gewoon de powerset?).

Free translation: Is 2^N just another notation for the set of all subsets of N, i.e., the powerset.

Answer

Yes that is right. 2^N is a notation for all the maps from N to a set of two elements, e.g., {0,1}. It is easy to see that each set can be seen as such a map and each map can be seen as a set: A function has value one on some number if and only if that number is in the set represented by that function.

Question

I've had some problems with understanding the proof of Theorem 6.2.3 in Cooper's book. They describe the construction of a simple set. 1. To me it is not clear what they mean by "stages 0, 1, ..., s, ..." . 2. They want to give a description of the enumeration algorithm such that it is clear that this algorithm induces a computable function. I doubt that they succeed in this. Something in (1) is just wrong, as their description is very vague, I cannot really see what. Given some e, we have to decide whether P_e holds or not. For this we have to decide whether W_e is infinite and, if that is the case, whether W_e contains some element that we already enumerated into our set. Both tasks seem to be quite incomputable. Or do they intend to 'label' the P_e's as /satisfied/ whenever having applied (2)? That will not work either. Maybe you already gave a clearer proof during the lesson that I missed. However, I finally found something in Terwijn's syllabus, p. 25 bottom. He gives the same proof as Cooper, but much clearer on both points that I did not understand. Having read the proof in Terwijn, I think that Cooper's proof is simply false. If that is so, it should be put on the list of errors and misprints.

Answer

As to point (1), I was pretty annoyed myself too to read this. Therefore, in class I specified this better. We considered pairs (e,s) and then the minimal such pair which has not yet been dealt with for which there is an element larger than 2e in W_{e,s}. And such an element was added in a new stage. After giving a formal specification/construction we made some remarks on how to de the verification. Point (2) is a Bis of point (1) and I agree wiht you that it is not good to be so vague as it is not a lot harder to be clear. It is good to consult other sources too. Terwijn's reader is an excellent source but one can also resort to classic textbooks like Odifreddi, Rogers or Soare.

Question

Answer


Joost Joosten
Last modified: Mon Dec 18 17:04:42 MET 2006