Velkommen til Københavns Universitets kursuskatalog
NDAA09007U Computability and
Full Degree Master
C (Mon 13-17 + Wednes 8-17)
Continuing and further
Study Board of Mathematics and Computer
Department of Computer Science
Christian Wulff-Nilsen (7-6e72726f72727d43676c316e7831676e)
Saved on the
In computing, there is continual tension between time usage and
space usage, and what can be computed and what cannot be computed
at all. The purpose of this course is to explore these
Complexity classes (P, NP, PSPACE, EXPSPACE, L, and NL)
At course completion, the successful student will have:
Computational models such as finite automata, pushdown
automata, and Turing machines, the languages recognized by some of
these models, and techniques for showing their limitations, such as
the pumping lemmas for regular and for context-free languages.
The power and limits of algorithmic solvability, with focus on
the computationally unsolvable Halting problem.
The reducibility method for proving that additional problems
are computationally unsolvable.
How to analyze algorithms and their time and space complexity
and how to classify problems according to the amount of time and
space required to solve them.
Known computational problems that are solvable in principle but
not in practice, i.e., intractable problems.
Reading and writing specifications of languages using
computational models and grammars.
Classifying given languages according to type (regular,
context-free, etc.) and algorithmic problems according to
complexity (time and space).
Showing the equivalence between certain machine models.
Presenting the relevant constructions and proofs in writing,
using precise terminology and an appropriate level of technical
Reason reliably about languages and computational models and
their strengths and limitations, and about the complexity of
algorithms and algorithmic problems.
Analyze and design languages, abstract machines, and
Communicate effectively about the theory of computation, both
for accessing advanced topics from the research literature, and
convincingly presenting the results of own work.
Is expected to be: Introduction to the Theory of Computation,
Michael Sipser, second edition, Course Technology. See Absalon when
the course is set up.
Teaching and learning methods
The course "Logik i datalogi" or some
math courses such as "Diskrete Matematiske strukturer
(DIMS)" would be useful, but are not
The student must participate in lectures and
solve exercises during the course. Assignments will be made each
week and be due in the following week. 5 assignments out of the 7
must be completed by the due date and approved to qualify to take
Written aids allowed
7-point grading scale
No external censorship
Several internal examiners
The re-exam will also be a 4 hours written exam,
unless there are 10 or fewer students signed up, in which case it
will be an oral exam (25 minutes oral exam without