Kaisa_2012_3_photo by Veikko Somerpuro

We start classes via Zoom from 18.03

From Turing machines to priority arguments.

We go through the basic theory of computability as given in N. Cutland's text "Computability: An Introduction to Recursive Function Theory." Different models of computability are studied: Post Systems, Turing Machines among others. We then prove basic undecidability results. We end with a sampling of the so-called priority arguments: the Friedberg Muchnik theorem, the 1-1 enumeration theorem and others. Students team up to present these as 2/3 of their final exam. (The other 1/3 of the students grade is based on work done in the example classes.)

Enrol

Timetable

Here is the course’s teaching schedule. Check the description for possible other schedules.

DateTimeLocation
Mon 13.1.2020
16:15 - 18:00
Wed 15.1.2020
10:15 - 12:00
Mon 20.1.2020
16:15 - 18:00
Wed 22.1.2020
10:15 - 12:00
Mon 27.1.2020
16:15 - 18:00
Wed 29.1.2020
10:15 - 12:00
Mon 3.2.2020
16:15 - 18:00
Wed 5.2.2020
10:15 - 12:00
Mon 10.2.2020
16:15 - 18:00
Wed 12.2.2020
10:15 - 12:00
Mon 17.2.2020
16:15 - 18:00
Wed 19.2.2020
10:15 - 12:00
Mon 24.2.2020
16:15 - 18:00
Wed 26.2.2020
10:15 - 12:00
Mon 9.3.2020
16:15 - 18:00
Wed 11.3.2020
10:15 - 12:00
Mon 16.3.2020
16:15 - 18:00
Wed 18.3.2020
10:15 - 12:00
Mon 23.3.2020
16:15 - 18:00
Wed 25.3.2020
10:15 - 12:00
Mon 30.3.2020
16:15 - 18:00
Wed 1.4.2020
10:15 - 12:00
Mon 6.4.2020
16:15 - 18:00
Wed 8.4.2020
10:15 - 12:00
Mon 20.4.2020
16:15 - 18:00
Wed 22.4.2020
10:15 - 12:00
Mon 27.4.2020
16:15 - 18:00
Wed 29.4.2020
10:15 - 12:00

Other teaching

14.01. - 25.02.2020 Tue 12.15-14.00
10.03. - 07.04.2020 Tue 12.15-14.00
21.04. - 28.04.2020 Tue 12.15-14.00
Juliette Kennedy
Teaching language: English

Material

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

Other

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