Alphabetes and languages–Chomsky’s Hierarchy
Finite Automata – Non Deterministic Finite Automata-–
Contex-free grammars- Pushdown automata- Non deterministic pushdown –
Turing Machine – Non deterministic Turing Machine – Universal Turing Machine- RAM model -
The Church-Turing thesis – The halting problem – Undecidible problems
The class P- The Class NP – Polinomial reductions - The class NP-complete-
