Computability (2010/11, Master of Science in Computer Science)

Information

This page provides some information about the Computability course.

The syllabus can be found on the Esse3 page.

Here are my short notes for the course.

These are work in progress, and may be updated at any time until the very end of the course.

There will be a mandatory written test and a mandatory oral test.

About the written test:

This is an open book test. You can refer to books, notes, etc.
No laptops during the exam. This is because nowadays laptops have wireless network cards, so they allow you to ask others for help. No cell phones or other potential communication devices, either.
Please have your ID with you (e.g. a passport).
You will be asked to solve several exercises. Refer to the questions of the 2008 and 2009 exams for examples. No theoretical question (i.e. one that can be solved by copying from a book) is asked here.
Evaluation: I am providing a short list of specific mistakes, which I found to be (sadly) common. If one of these is found in your answers, a harsh penalty may be applied.
In general, the principle is ``quality over quantity''. A few correct answers to some of the questions can award some nice points. Less so when for each correct answer I can find 3 or 4 wrong ones.

About the oral test:

This is a closed book test. You can not refer to books.
You can be asked to state and prove one of the theorems from my notes.
Avoid blindly memorizing proofs without understanding them. I will likely interrupt you in the middle of a proof, and require some more details about a specific step.
You can be asked to solve a small exercise as well.
You will have a reasonable amount of time to answer. I never expect an immediate answer. If you are unsure about your answer, you can ask for some time (say, up to 5 minutes) to make your mind clear before answering.
Correctness of answers is what will be evaluated; speed is much less important.

Remember to register to the exam sessions on Esse3.

The students wishing to improve their understanding of mathematical proofs are referred to the following basic logic and set theory books:

Elements of logic via numbers and sets, D.L. Johnson, Chapter 6
Proofs in Mathematics: an Introduction, J. Franklin and A. Daoud (Quakers Hill Press, 1996)
A Brief Introduction to Proofs, W.J. Turner
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

Computability references and textbooks:

My notes (see above)
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.
An on line interpreter for the untyped lambda calculus. You want to set it on singlestep + normal order (= leftmost-outermost strategy).

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