Introduction to Theory of Computation

This class deals with fundamental questions: what is computable, what is not? What is provable and what not? What is computable with feasible effort. The concrete example ‘can RSA be broken with reasonable computation time?’ shows, that such fundamental questions have enormous practical importance.

Although we will be dealing with a very wide range of questions for the better half of the lectures, we are forced to rely on only two proof techniques: diagonalization and simulation theorems between computational models. We simply do not have other techniques which work (for now, but that is the case since many decades).

Planned course content by weeks:

1. Regular expressions, finite automata and nondeterminism.
2. Context free languages and pushdown automata.
3. Context sensitive languages, type-0 languages and Turing machines.
4. Recursive functions, computability and decidability.
5. Undecidable problems and the recursion theorem.
6. Proof Systems.
7. Gödel’s incompleteness theorems.
8. Turing machine complexity classes.
9. Complexity hierarchies.
10. Speed up and Gap theorem.
11. NP completeness.
12. More about complete problems.
13. Time versus space.
14. Determinism versus nondeterminism.
15. Applications of Kolmogorov complexity.

During these lectures, we will cover fundamental results present in a more conventional treatment of the subject as well. In particular we will treat: The Recursion Theorem, the two fundamental incompleteness theorems of Gödel, the speed up and gap theorems of Manuel Blum and Allan Borodin, two fundamental separation theorems between the classic complexity classes of complexity theory, Applications of Kolmogorov complexity.

Literature used:

• Introduction to the Theory of Computation. Sipser M., Edition 3, engage Learning, (ISBN 1133187811; 9781133187813), (2012).
• Formal Languages and Their Relation to Automata. Hopcroft, J. E.; Ullman, J. D., Addison-Wesley Series in Computer Science and Information Processing. Reading, Mass. etc.: Addison-Wesley Publishing Company. X, 242 p. (1969).
• Compilers. Principles, techniques, and tools. Aho, Alfred V.; Lam, Monica S.; Sethi, Ravi; Ullman, Jeffrey D., Edition 2, Boston, MA: Pearson/Addison Wesley (ISBN 9780321486813; 9780321491695). xxiv, 1009 p. (2007). Because of its cover commonly known as ‘the dragon book.’
• Komplexitaetstheorie. Paul W., Teubner (1978). It is in German and out of print, but I am optimistic that the slides will reflect the author’s intentions fairly well.
• Various original articles.

Administration for 2025 class

The course is held on Tuesdays at 17:00-18:50 and Wednesdays 16:00-16:50. Please check your calendar for weekly updates. The location is auditorium A1 at KIU Campus. Slides and weekly exercises are available in the “Class Material” folder on the course channel in MS Teams.

Lectures are also recorded and uploaded to YouTube. Below is the playlist.

What actually happens in class is usually different from what was intended. Here, I will outline for students what was actually covered and where to find the material.

Week 1 - Regular expressions, Finite Automata. Slides: TCS-1.

Week 2 - Nondeterministic finite automata. Slides: TCS-2.