Faculty of Science

Objectives

To provide students with a detailed understanding of the basic concepts of abstract machine structure and information flow.

Contents

Deterministic and non-deterministic finite automata; formal languages; pushdown automata and context-free language; time and tape bound; Turing machines; decision problems; decomposition theory; Propositional calculus; quantification theory; abstract complexity; Definitions of computability and their equivalence; polynomial-time computability; classifying unsolvable problems; degrees of insolvability and Post’s problem.