Tik79.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 Turingdecidable,
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:
 define a finite state automaton that correspods a regular
expression
 define a pushdown automaton that correspods a given context free grammar G

define a context free grammar that defines language L = {x  P(x) }

transform a given finite state automaton to an equivalent
deterministic finite automaton
 prove that a given language L is not context free
 prove that a function f(x,y) is Turing computable
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).
 The first 13 pages of each chapter give an overview of the subject
 The definitions of the basic concepts (words in bold)
 Different proofs and constructions (these are often parts of the
proofs), the most important proofs are mentioned below.
 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
"LewisPapadimitriou: 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ödelnumbering 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.
 Chapter 1, especially 1.71.8 [1.8  1.9]
 Chapter 2
 Chapter 3, except 3.7 [3.6 and pages 127  130]
 Chapter 4
 Chapter 5, except 5.6, Especially 5.3 [chapters 56, except
6.4.2  6.4.3 and 6.5 . Especially 6.1]
 From chapters 6 and 7 parts 6.1, 6.4, and 7.17.2. [7.1, 7.4, and
7.5]
Most important theorems and lemmas
 T2.2.1 [T2.3.1]
 T2.3.1 [T2.4.1]
 T2.3.2 [T2.5.1]
 T2.4.1 [T2.6.1]
 T2.6.1 [T2.4.2]
 T3.4.1, L3.4.1, L3.4.2 [T3.4.1, L3.4.3, L3.4.4]
 T3.5.1
 T3.5.3
 T4.5.1 [L4.6.1, T4.6.1]
 T4.6.2 [L5.2.1, T5.2.1]
 T4.7.1 [T5.6.1]
 [T5.5.1] (the equivalence of grammars and murecursive functions,
it follows from T4.6.2 and T4.7.1)
 T5.3.1 [T6.1.5]
 [T6.2.1  T6.2.4] (relation between Turingacceptable and
Turingdecidable languages)
 T5.4.2 [T6.3.1  T6.3.2]
 T5.5.2 [T6.4.1]
 D6.1.1 [D7.1.1,D7.4.1]
 [T7.1.1] (Any Turing machine can have an arbitrary linear speedup)
 D6.4.1 [D7.4.2]
 T6.4.1 [T7.4.1]
 D7.1.1 [D7.5.1, D7.5.2]
 D7.1.2 [D7.5.3]
 T7.1.1 [T7.5.1]
 T7.2.2 [T7.5.2]