Theory of Computing

A tantárgy neve magyarul / Name of the subject in Hungarian: Számításelmélet

Last updated: 2010. november 11.

Budapest University of Technology and Economics
Faculty of Electrical Engineering and Informatics

Mérnök informatikus szak

BSc képzés

Course ID Semester Assessment Credit Tantárgyfélév
VISZA081   3/1/0/v 4  
3. Course coordinator and department Dr. Katona Gyula,
Web page of the course
4. Instructors








Assoc. professor


Department of Computer Science and Information Theory


Katalin FRIEDL


Assoc. professor


Department of Computer Science and Information Theory




Assoc. professor


Department of Computer Science and Information Theory




Assistant lecturer


Department of Computer Science and Information Theory




Assoc. professor


Department of Computer Science and Information Theory




Assoc. professor


Department of Computer Science and Information Theory


7. Objectives, learning outcomes and obtained knowledge

In the first part of this course we introduce different theoretical models for computing. There are ones that are easy to describe but have limited power, and there are more complicated ones with more power. The first one is the finite automaton. On one hand it is used directly, since it is easy to build them to perform simple tasks. Many electronic devices contain basically one chip, which is really a finite automaton. On the other hand, it can be used as a programming technique, too. It helps in code optimization and verification. Unfortunately, not every problem can be solved by them, we will show their limits.

The next model is the pushdown automaton. It has more power, but still is not too hard to build one. It is used widely in compilers, for example.

The last important model is the Turing machine. It is considered to be the model of an everyday computer. It is very powerful, one can solve most of the real life problems with it, especially if there is no time limit. We will define many variants as well and see how these variations change its power.

In the second half of this course the first important question that we answer: Is there an algorithm for any problem? If there is an algorithm, can we implement it by a given computational model? It turns out that there are some interesting problems that seem to be much more difficult than others even if the computers would be extremely fast.

Another question is that what happens if we have limited resources. Time and/or space is limited for the computation, which is the case in real life.

Scientists over centuries tried to solve some difficult algorithmic problems, but failed to succeed in some cases. Is it the case that they are not clever enough? Or there is no algorithm at all? Is there something in between these two possibilities?


8. Synopsis

First half-semester

  1. Finite automata, non-deterministic finite automata


  2. Regular and non-regular languages, pumping lemma.


  3. Pushdown automata, context-free languages,


  4. Turing Machines and variants, universal Turing machines.


  5. The existence of universal Turing machines.


  6. Recursive functions. Recursive, recursively enumerable languages.


Second half-semester

  1. Algorithmic decidability,


  2. Halting problem and other undecidable problems.


  3. Storage and time, general theorems on space and time complexity


  4. Non-deterministic Turing-machines.  NP and co-NP.


  5. Cook's theorem: SAT is NP-complete.


  6. Other NP-complete problems.


9. Method of instruction Lectures and recitations


10. Assessment A homework set of 4 problems will be given out on weeks 2 – 5 and on weeks 8-11.


Grading will be based on the following criteria:


- Homeworks  60 points


- Final exam     40 points


12. Consultations You can reach the instructor at the following e-mail address for consultation:


Gyula Y, KATONA:


13. References, textbooks and resources Michael Sipser: Introduction to the Theory of Computation, Thomson Course Technology, 2006


14. Required learning hours and assignment
Number of contact hours




Preparation to the classes




Preparation to the tests







Assigned reading




Preparation to the exam








15. Syllabus prepared by








Assoc. professor


Department of Computer Science and Information Theory