Introduction to various models of computation. Machines, languages and grammars.
Turing-computability. Universal Turing Machines. Recursive functions. Church’s thesis.
Godel’s completeness and incompleteness theorems. Closure properties and complexity
classes of languages. Decidability, undecidability and partial decidability.