Kaisa_2012_3_photo by Veikko Somerpuro

Computability Theory

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.

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.

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