Computation and Complexity Theories


This subject is about the model of Turing Machine and the idea of non-convergence as starting point of the Theory of Calculability. The last topic of the subject is about the Theory of Complexity.

1.- Introduction
    1.1. Motivation and Objectives of this subject
    1.2. Chomsky's hierarchy

2.- Turing Machine
    2.1. Description and Representations
    2.2. TM to recognize Formal Languages
    2.3. TM to compute Mathematical Functions
    2.4. The TM Execution Cycle
    2.5. Deterministic TM
    2.6. Non-Deterministic TM
    2.7. The Universal TM

3.-  An Introduction to the Theory of Calculability
    3.1. Some Limitations of TM
    3.2. Calculability Principles
    3.3. The Theory of Calculability

4.- An Introduction to the Theory of Complexity
    4.1. Computational Complexity
    4.2. Basic Complexity Classes
    4.3. The Classes L and NL
    4.4. The  Classes P, NP i CoNP
    4.5. The Classes EXP i NEXP
    4.6. Complexity Principles
    4.7. The Theory of Complexity