Computability (2011/12, 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.

Notes

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. The Nov 30 version contains all the material; further updates only contain clarifications (and possibly corrections).

• Notes - (minor changes only, last updated on 2012-04-18)
• Old notes - (last updated on 2011-11-30)

Office Hours (Ricevimento Studenti)

There is no fixed schedule for office hours. Rather:

• For quick questions, you can send me an email.
• For more complex questions, you can ask for an appointment as follows:
  • Check all of the following links for upcoming appointments:
    • Office hour (A)
    • Office hour (B)
  • If all the above polls are closed, send me an email, specifying one or (better) more dates in which you are available.
  • Please do not ask an appointment for the next 0, 1, or 2 days, since that makes it hard to agree on a common date with other students.
  • No more than one appointment each week.
  • Try to form a small group with other students if you think others want to ask questions as well.
  • The office time is shared among all the students.
  • Prepare specific questions in advance. Asking to explain a whole chapter leads to no useful answer.
  • Office hours are not a substitute for classes.

Exams

Here you can find some questions from my previous exams. You will also find many questions answered here.

• Written Exams 2008 (with answers)
• Written Exams 2009 (this was a closed book exam, so you will also find questions about theory here)
• Written Exams 2010 (with answers)

Exam Procedures

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

About the written test:

• Please have your ID with you (e.g. a passport).
• 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.
• You will be asked to solve several exercises. Refer to the questions of the previous exams for examples. No theoretical question (i.e. one that can be solved by copying from a book) is asked here.
• Evaluation. To award points, you need to provide a correct answer to the questions and an adequate justification for it. A correct answer without justification awards instead no points. Further, severe mistakes negatively affect your score - it is in general advisable to refrain from answering rather than making a blatant assertion of an obviously false property. I am providing a short list of specific mistakes. If one of these is found in your answers, a harsh penalty will be applied.
  • Common mistakes in written tests
• Answers to the questions are provided before the oral test (either on this web site, or at the latest in class just before the oral test begins).
• Results of the written tests will not made available until the day before the oral test.
• If you ask for it, you can examine your written test after the evaluation on the oral exam day, following this procedure:

  1) if you passed the written exam, you can ask to check your written test during the oral exam. Any discussion you may wish to start regarding your written test will be evaluated for the oral test.

  2) if you did not pass the written test, you can examine yours right before the end of the oral tests.

About the oral test:

• Please have your ID with you (e.g. a passport).
• This is a closed book test. You can not refer to books.
• You can be asked to provide one of the definitions from my notes. (The ones to remember are marked as such.)
• You can be asked to state and prove one of the theorems/lemmata from my notes. (The ones to remember are marked as such.)
• A non-exhaustive list of questions is provided
  • Common questions
• 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.
• 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.
• Correctness of answers is what will be evaluated; speed is much less important.
• Final mark. The final mark is your written test mark adjusted according to the oral test.
  • If your written test mark is under 18, the adjustment can be +2 at most.
  • If your written test mark is between 18 and 23, the adjustment can be +3 at most.
  • If your written test mark is above 23, the adjustment can be +4 at most.
  • There is no lower bound for the adjustment, which can therefore be -30.

Exam Dates

Remember to register to the exam sessions on Esse3. Failure to do so results in the impossibility to take the exam. (In case of technical problems, send me an email before the registration period runs out).

• Session 1 written test: 2012-01-19 09:00 room A105 - answers - results
• Session 1 oral test: 2012-01-26 09:00 room A107
• Session 2 written test: 2012-02-06 14:30 room A105 - answers - results
• Session 2 oral test: 2012-02-16 09:00 room A107
• Session 3 written test: 2012-06-11 15:00 room A205 - answers - results
• Session 3 oral test: 2012-06-21 09:00 room A210
• Session 4 written test: 2012-07-10 09:00 room A104 - answers - results
• Session 4 oral test: 2012-07-16 09:00 room A222
• Session 5 written test: 2012-09-03 09:00 room A104 - answers - results
• Session 5 oral test: 2012-09-10 09:00 room A208

Reminder: there will be NO other exam sessions beyond the mandated five per year. This is communicated to students every year during the first lecture.

Also, starting from 2011, I will try my best to avoid changing the exam dates so that students can plan everything in advance (e.g. buying plane tickets). Because of this, I can not move exam dates, even in the unfortunate event that they overlap with, or are very near to, other exams. Please also understand that the current system does not allow me to predict overlaps: I can only discover them once they are published on ESSE3, and by that time it is too late.

References

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

Home - Teaching - Computability

Roberto Zunino, 2012