Tik-79.148 Introduction to theoretical computer science

Requirements, spring 2001

The goal of the coures is to introduce the basic concepts of theoretical computer science. After the course the student should be able to define, for example, what means Turing-decidable, grammatically computable, primitive recursive function, regular language, etc.

Moreover the student must know how to apply these concepts. in different constructions and proofs. Examples of these are:

The course includes a lot of material. Therefore it should be studied in the following order (because it is quite probable that students have limited time for this course).

  1. The first 1-3 pages of each chapter give an overview of the subject
  2. The definitions of the basic concepts (words in bold)
  3. Different proofs and constructions (these are often parts of the proofs), the most important proofs are mentioned below.
  4. Other proofs.

The concepts of the course can be put into the language hierarchy of Chomsky. This can help to remember things.

Parts of the textbook that are inluded in the course

"Lewis-Papadimitriou: Elements of the theory of computation" There are currently two different editions of the course book (1983 and 1998 ones). There are a few differences between the editions, but both may be used. The newer one's presentation is somewhat clearer, but the topic of Gödel-numbering is left out of it, so you should that part from the older edition.

Below numbers [in brackets] are from old edition, if the numbering of the sections or theorems differ between editions.

Most important theorems and lemmas