Computability (2008/09, Master of Science in Computer Science)

Notes

Here are my short notes for the course.

The "9 Dec" version contains all the topics; further revisions are only meant to clarify some aspects, fix typos, etc.

• Notes - 12 Dec 2008
• Notes - last update 27 May 2009

Also see the Esse3 page for the course.

Exams

Midterm 2008-10-29: answers

Endterm 2008-12-17: answers

Session 1:
Written Exam: 2009-01-20 14:00 room 202 - answers
Oral Exam: 2009-01-26 9:00 room 201

Session 2:
Written Exam: 2009-02-06 8:30 room 202 - answers
Oral Exam: 2009-02-13 9:00 room 109

Session 3:
Written Exam: 2009-06-03 14:00 room 103 - answers
Oral Exam: 2009-06-15 9:00 room 201

Session 4:
Written Exam: 2009-07-06 14:00 room 109 - answers
Oral Exam: 2009-07-14 9:00 room 207

Session 5:
Written Exam: 2009-09-03 14:00 room 109 - questions
Oral Exam: 2009-09-11 10:00 room 107

How does the written exam work? It is made of two parts: part 1 is equivalent to the midterm, and part 2 is equivalent to the endterm.

• At the beginning of the exam, you can read both parts.
• After 90 minutes, you can stop, and give me your answers to either part 1 or part 2: doing this, the corresponding midterm/endterm mark is replaced with the (possibly lower) score of your answers.
• After 180 minutes from the beginning, you can give me your answers to both parts, and replace both scores.
• At any time (even after 180 minutes) you can leave without providing answers. In this case, your midterm/endterm scores are unaffected.
• This is a open book test. You can use books, notes, etc. Potential communication devices are not allowed (cell phones, laptops, etc.). Please bring your ID.

How does the oral test work? I may ask you to provide a proof for any of the theorems/lemmata that are in the notes. I may ask you about the definitions that are in the notes. I may ask you to solve a short exercise.

References

Textbooks:

• N.J. Cutland, Computability, Cambridge University Press
• H.P. Barendregt, The Lambda Calculus - its syntax and semantics, North Holland
• H. Rogers, Theory of recursive functions and effective computability, McGraw-Hill.

I will try to point out in my notes which parts of the books above are actually used in the course.

Basic set theory references:

• Introduction to the foundations of mathematics, R. L. Wilder, Chapter 4
• Sets, functions, and logic : an introduction to abstract mathematics, K. Devlin, Sections 4.6, 4.7
• Elements of logic via numbers and sets, D.L. Johnson, Chapter 6

Home - Teaching - Computability

Roberto Zunino, 2009