The first lecture is historical and is based on the attached papers by Kennedy and Gandy.
All exercises in chapter 1 of Cutland's text.
In chapter 2 of Cutland do problems in the attached.
Complete the proof that the classes of the URM-computable functions and the partial recursive functions coincide. (This os theorem 2.2 in the text.)
Do all the problems in Cutland chapter 3 EXCEPT for the last set at the end of the chapter. OMIT also the second problem of the second set, i.e 6.3, problem 2.
The appendix to chapter 5 gives a detailed proof of the computability of the universal function psi_U^(n). Go through the proof and be prepared to present parts of it at the blackboard in class.
Homework for April 10
1. Give a complete proof of the undecidability of the first order predicate calculus. (I.e. flesh out theorem 5.1 in detail.)
2. Read and discuss this article: http://people.ucalgary.ca/~rzach/static/cshpm.pdf
Homework for March 23
Prove Rice's theorem from the Rice-Shapiro Theorem. This is exercise 12 on p. 133, which contains a hint.
Do exercises 8, 10, 13 on pages 132-33.
Second set of questions: on p. 138-9: 1,2,5,7,8,9
Homework for March 31
p. 141: 1,2,3
p. 152: In note 3 it is claimed that "we can demonstrate the mere existence of an undecided statement using any non-recursive r.e. set in place of K." Prove this.
p. 160: 1-5
p. 165: 3,4,6
Homework for April 7
Prove theorem 5.10, p. 178
Prove theorem 5.12, p. 179
Finish reading chapter 9.
The course is based on Cutland's text. Example classes are given, and work done in those sessions makes up for 1/3 of the final grade. The other 2/3 of the grade is based on your in class presentation.
The example classes meet Tuesdays 12:15 - 14:00 in Exactum, C322.
To get a grade for the example class portion of the class you must hand in 75% of the homeworks, either in class or send a scanned copy to Otto.email@example.com