Recursion Theory, Spring 2003

Seminar / reading group / project / PhD course

The exam (for the 12-week project, not the PhD course) takes place on Tuesday, June 24 in room 3.08 starting at 9.00. Our internal censor is Lars Birkedal from IT-højskolen. Good luck!

Literature. J. R. Shoenfield. Recursion Theory. Springer-Verlag 1993 (reprinted by A K Peters 2000, ISBN 1-56881-149-7).

Episode 1, February 6, 2003. Sections 1 to 4 presented. Homework Exercises (corrected February 10) available for download. Nina's solution to Exercise 6 is now written up.

Episode 2, February 13, 2003. We have discussed sections 5 through 7. The discussion unearthed an interesting question about whether there is a single `function algebra term' describing definition by cases for partial (recursive) functions. This question became Exercise 6 in Homework Exercises (corrected February 20).

Episode 3, February 20, 2003. We have discussed homework exercises, as well as sections 8 and 9 from the textbook. We focused our attention on the fundamental results of Recursion Theory: the Normal Form, Enumeration, Parametre, and Recursion theorems, as reinforced by Homework Exercises. We have also agreed to accept Church's Thesis as a working hypothesis, at least unless and untill proven wrong.

Episode 4, February 27, 2003. Sections 10 (Volodya) and 11 (Bodil) were presented. Homework Exercises available for download.

Episode 5, March 6, 2003. Nina told us about the class of primitive recursive functions and about the construction and properties of the Ackermann function. We discussed the exercises and sections 12 and 13 from our textbook. Homework Exercises (corrected March 13) ready to go.

Episode 6, March 13, 2003. We talked about sections 14 and 15 and selected Homework Exercises. Volodya presented Proposition 15.5 (The Friedberg-Muchnik Theorem). New batch of Homework Exercises (corrected March 20) awaits solutions.

Episode 7, March 20, 2003. We shared our impressions of section 16. Jacob entertained us with Proposition 16.4 talking about things highly complicated. New Homework Exercises are best served at room temperature.

Episode 8, March 27, 2003. We discussed section 17, and Jacob unexpectedly presented Proposition 17.6. We also recalled some old exercises and listened to an erratic account of effectively inseparable pairs of recursively enumerable sets. Don't forget the new Homework Exercises (corrected April 3).

Episode 9, April 3, 2003. Section 18 was found unproblematic by all those present, and mentioned only briefly. Instead, we rather thoroughly went through Homework Exercises from Episode 8. We also briefly contemplated a category made of recursively enumerable equivalence relations. Participants clearly expressed a preference for not having their homework exercises any more routine then they have been up till now. Hopefully, the new Homework Exercises (corrected April 10) won't score too heavily on the routine-o-meter.

Episode 10, April 10, 2003. Sections 19 and 20 and homework exercises were discussed. A topological perspective on the projective hierarchy considered. The book is finished, but Homework Exercises (corrected April 24) are not.

Episode 11, April 24, 2003. Three hours proved to be insufficient for Rasmus to construct a finitely presented group with an undecidable word problem. We'll decide next time what to do about him.

Episode 12, May 1, 2003. Jacob gave a very careful and detailed account of the definition of Kleene's O, the properties of the associated ordering, and the construction of a recursive ordinal addition function on O.

Extra Episode 13, May 8, 2003. Rasmus successfully worked through the obstacles to construct groups with undecidable subgroup and word problems.

The subject. Recursion Theory is the study of computability properties of objects like functions and sets of natural numbers, sets of reals etc. It also addresses decidability of problems naturally occurring in mathematics or logic. For an undecidable problem, it creates a framework for the quetion `How undecidable?', and for many specific problems, answers this question.
We are going to cover, among others, the following topics:
- Recursive (computable) functions
- Recursive and recursively enumerable sets
- Turing reducibility and degrees of unsolvability
- Undecidable theories and undecidable word problems
- The arithmetical hierarchy
- The analytic and projective hierarchies

Scope and nature of the seminar. In the sping semester of 2003 we plan to hold a seminar on Recursion Theory. This will be centered mainly around J. R. Shoenfield's Recursion Theory lecture notes. This booklet is relatively small (78pp.) and it is entirely realistic to cover all of it within one semester in some detail. In fact, this would be our minimum goal. It is also hoped that we shall have time and energy to supplement it with some exercises and, as the needs and wishes of participants may suggest, also review a few background or advanced topics. It is expected that by the end of the course the participants should be prepared for studying advanced books and research papers in the subject.

We are going to discuss the reading material, take turns making short presentations, and solve problems.

Prerequisites. The main prerequisite is a decent level of mathematical maturity. Some knowledge of logic and/or computer programming would be nice but not strcitly necessary. Courses like Logic (F. Topsøe, University of Copenhagen, E2002) or Logic and Computability (V. Yu. Shavrukov, IT-højskolen, F2002) should be amply sufficient for logic. As for computer programming, down here at IT-højskolen it seems anybody knows more about that than I do.

Formalities (for those interested in ECTS points). The seminar / reading group is formally considered a 12-week project. This means that students form IT-højskolen will be able to get an appropriate amount of ECTS points provided they pass rather than fail (we are talking 7.5 ECTS here). The same concerns students from the University of Copenhagen, as these two institutions have typically been able to arrange smooth transfer of credits in both directions.

Projects at IT-C require a little bit of form-filling. There are, in principle, three stages. The first two are called `Vejlederansogning' and `Projectaftale' respectively. These two can probably be combined into a single procedure, and the form for both stages is the same. You can download a model project agreement in .doc or .pdf format. You'd still need to fill in your details, have the `vejleder' (that would be me, V. Yu. Shavrukov) sign it, and submit it to IT-højskolen's Study Administration. You can also suggest adjustments to the project description that we can discuss before commiting to a project. The deadline for submitting `Vejlederansogning' is February 3, 12.00, and February 24, 12.00 for`Projectaftale'.

Students based outside IT-højskolen (e.g. at the University of Copenhagen) need to obtain a written approval for the project from the Study Board at their home institution so that ECTS points scored at IT-højskolen count as such back at home. On top of that, you need to submit a written request to be admitted as a guest student for project participation to the Study Administration of IT-højskolen. The request has to have the following attachments:
- The letter from your institution's Study board approving your participation
- A copy of your bachelor's diploma
- `Projektaftale' signed by the `vejleder' (as described above).
Sounds complicated? It is. When I asked a study administrator about the deadline for all this, I was told that this `should be ideally done in January'.

PhD students. PhD students, who normally don't do projects, can nevertheless participate in the seminar and get credits for participation. From the viewpoint of a PhD student, the seminar is a `PhD course'. Our seminar has been officially approved by IT-højskolen's PhD Study Board as a PhD course. Our current investigations are aimed to determine whether the PhD student(s) attending the course with an eye to evaluation need to register this intention with some authority or other.

Evaluation. Participants requiring evaluation will have to submit a written report at the end of the project (by May 2, 12.00) and take an oral exam sometime in June. We have applied for a pass/fail exam with internal censor. The report may consist of notes for one's presentation, solutions to a selection of exercises, exposition of a particular topic, or something similar. This need not involve a great lot of writing. The oral exam will mainly focus around the report. The quality of one's participation in the seminar will be taken into account for final evaluation.

Contact. Those interested in taking part, please take up contact with Volodya Shavrukov (volodya@it-c.dk), IT-højskolen, Glentevej 67, 2400 København NV, room 2.09, +45 38168907.