Recursion Theory
2004/2005; 1st Semester; period a.

Click here to go back to the home page of the class.

Week

Date

Section

Homework sets
1 Sep 7 1.1, 1.2, 1.3, 1.4, 2.1


Due Sep 14:
download here
Sep 10 Practice session


Exercises for practice:
download here
(not for turning in)
2 Sep 14 2.2, 2.3


Due Sep 21:
Exercises 2.2.12, 2.2.18, and 2.3.7 from the book.

Note: For problem 2.2.12, The book suggests that you come up with an algorithm to calculate the function you need, and use Church's thesis. For this homework, however, make sure that your answer consists of the formal definition of the function (that is, a definition using composition, primitive recursion, etc), You can of course use an algorithm as a help to get to your final answer, though.).

Sep 17 Practice session


Exercises for practice:
Exercises 2.2.11, 2.2.16, 2.2.20 and 2.2.22
(not for turning in)
3 Sep 21 2.4, 2.5 (sort of)


Due Sep 28:
download here
Sep 24 Practice session


Exercises for practice:
download here
(not for turning in)
4 Sep 28 4.1 - 4.3


Due Oct 5:
download here
Oct 1 Practice session  
5 Oct 5 4.4-4.5 and 5.1-5.2


Due Oct 12:
download here
Oct 8 5.2 and 5.3


Exercises for practice:
(not for turning in):
5.1.13, 5.2.9, 5.2.12, 5.2.15, 5.2.17, and 5.2.19.
6 Oct 12 5.4 and 3.1


Due Oct 19:
download here
Oct 15 Practice session


Exercises for practice:
(not for turning in):
5.3.8, 3.2.8, 3.2.9

Also: we proved that the set of all the indices of computable functions is not c.e. Prove that its complement is not c.e. either.

7 Oct 19 3.2, 6.1, 6.2


Due Nov 2:
(leave your work in my mailbox)
download here
Oct 22 6.2 and 6.3.  

Click here to go back to the home page of the class.