Elements of the Theory of Computation

Objectives

To introduce the concept of an algorithm and of a model of computation, namely of finite and infinite automata (pushdown automaton and Turing machine). To study the hierarchy of languages. To solve algorithmic problems through Boolean circuits andto classify their complexity in terms of circuit size and circuit depth.

Program

Finite automata; regular languages, regular expressions and regular grammars. Pushdown automata;
context-free languages and grammars. The concept of an algorithm according to Turing. Turing
machines. Universality. Register machines. The Church-Turing thesis. Chomsky hierarchy. Decidable
and undecidable problems. Complexity measures. Space and time bounded resources. Complexity
classes and complete problems. Boolean circuits and families of circuits. Sequential Boolean circuits.
Combinatorial Boolean circuits. Discussion of the equivalence between Turing machines and families of
circuits. Alternation. Complete problems for classes of Boolean circuits.

Teaching Methodologies

Exam/tests, possibly with minimum grade, complemented with continuous evaluation components.

Bibliography

Elements of the Theory of Computation, Harry R. Lewis e Christos H. Papadimitriou, 2015, 2ª Ed. Dorling Kindesley Pearson Education; Introduction to the Theory of Computation. Cengage Learning, Terceira edição, Michael Sipser, 2014, 3ª ed.; Computability and Complexity Theory, Steven Homer e Alan L. Selman, 2014, 2ª ed. Springer; Circuit Complexity and NeuralNetworks, Ian Parberry, 1994, MIT Press; The Nature of Computation, Christopher Moore and Stephen Merteen, 2011, OxfordUniversity Press.