Computability (2012/13, 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.

Assignments

Assignments will be given during the course. They are optional, anonymous, and do not affect the final score. Still, students are encouraged to submit their answers, so that they can be discussed during the tutoring activities.

• Assignments

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: 2013-01-18 09:00 room A103 - answers - results
• Session 2 written test: 2013-02-04 14:30 room A103 - answers - results
• Session 3 written test: 2013-06-10 14:30 room A103 - answers - results
• Session 4 written test: 2013-07-15 14:30 room A103 - answers - results
• "Fake" session 4.1: on ESSE3 you will find a session on date 2013-08-01. This was NOT a real exam session, and was used to enter some "thawed" marks from previous sessions, only.
• Session 5 written test: 2013-09-04 14:30 room A103 - answers - results

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

Home - Teaching - Computability

Roberto Zunino, 2012