Special Topics in Computer Science (CS493)

Theory of Computation

Fall Semester 2008

This course in Theory of Computation complements our courses on the design and analysis of algorithms: It explores the limits of what can be computed - and in particular which problems cannot be solved, neither efficiently nor at all: regardless of how smart an algorithm anyone is ever to invent! Such investigations give rise to a taxonomy of classes of computability and complexity, based on the important notion of completeness. This permits to judge whether a specific algorithm is optimal for some problem (and any attempts for further improvement thus bound to fail), or how far off from optimal it may be.

The course will take place in the first five weeks of the semester, from September 1 to October 1.


Martin Ziegler (Office: E3-1 3447, Phone: 5582) and Otfried Cheong (Office: E3-1 3434, Phone: 3542).


The class meets Monday, Wednesday, and Friday from 11:00 to 11:50 in room 2443 (class room 3) of the Computer Science Building (E3-1). Lectures are given in English.

Grading policy

Grading is based on homeworks (40%), a final exam (40%), and participation in class (20%).


There will be a final exam on October 13, from 11:00 to 12:30 in our usual classroom.


We will use these books as references. The first two should be available in the library, students do not need to buy them.

In addition, copies of the slides used in the class will be available.


Here is a rough list of what we will cover in each week of the semester.

Week 1 Turing machines, diagonalization, uncomputability of the Halting problem
Week 2 Higher degrees of uncomputability, Kleene's arithmetical hierarchy
Week 3 Space hierarchy theorem, time hierarchy theorem
Week 4 Relativizations of the P versus NP question
Week 5 Solution to Post's Problem

Course progress

The material covered in the lectures so far:

09-01 Introduction to Diagonalization and Computability Slides
09-03 Diagonal Language, Halting Problem, Undecidability Slides
09-05 Rice's Theorem, Oracle Computation Slides
09-08 Discussion of Homework 1
09-10 Arithmetical Hierarchy Slides
09-12 Time Hierarchy Theorem Slides
09-15 Chuseok Holiday
09-17 Discussion of Homework 2
09-19 Relativizations of "P versus NP" Slides
09-22 Discussion of Homework 3, Degrees of Undecidability Slides
09-24 Discussion of Bonus Exercise, Post's Problem Slides
09-26 Finite Injury Priority Diagonalization Slides
09-29 Discussion of Homework 4
10-01 Quine's theorem, Bonus material Slides
10-13 Final exam (11:00 to 12:30)


There will be one homework assignment per week, and you will have one week to complete an assignment. Programming homeworks are submitted by email to the instructor, theoretical homeworks must be submitted on paper and should be handed in at the beginning of class.

Bulletin board

We have a bulletin board for announcements and discussions. You can also post your questions there. Both Korean and English are acceptable on the BBS :-)

Otfried Cheong