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?

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

7. Algorithmic decidability,

    

8. Halting problem and other undecidable problems.

    

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

    

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

     

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

     

12. Other NP-complete problems.