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.
- Notes - (last updated on 2010-12-15)
Exams
Exam Procedures
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.
Exam Dates
Remember to register to the exam sessions on
Esse3.
- Session 1, written test: 2011-01-11 09:00 room 109, answers - results
- Session 1, oral test: 2011-01-18 09:00 room 106
- Session 2, written test: 2011-02-08 09:00 room 109, answers - results
- Session 2, oral test: 2011-02-15 09:00 room 106
- Session 3, written test: 2011-06-07 14:30 room 109, answers - results
- Session 3, oral test: 2011-06-22 09:00 room 108
- Session 4, written test: 2011-07-07 14:00 room 109, answers - results
- Session 4, oral test: 2011-07-14 09:00 room 108
- Session 5, written test: 2011-09-01 09:00 room 109 - answers - results
- Session 5, oral test: 2011-09-12 09:00 room 103
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 (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.
Home -
Teaching -
Computability
Roberto Zunino, 2010