# 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:

• 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).

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.

• Chapter 1, especially 1.7-1.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 5-6, 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.1-7.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 mu-recursive 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 Turing-acceptable and Turing-decidable 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]