### Timetable

### Material

The first lecture is historical and is based on the attached papers by Kennedy and Gandy.

### Tasks

#### Homework 1

All exercises in chapter 1 of Cutland's text.

#### Homework 2

In chapter 2 of Cutland do problems in the attached.

#### Homework 6

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.)

#### Homework 3

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.

#### Homework 4

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.

### Conduct of the course

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.rajala@helsinki.fi