Course Description
This module introduces the mathematical theory of computation. Several types of abstract computational machines (called automata) are introduced together with the associated theory of formal languages. A formal language is a set of words over a defined alphabet that are well-formed according to a specific set of rules, called the grammar of the language. After studying the relationship between automata models and classes of formal languages, this course addresses the fundamental question “What problems can a computer possibly solve?” by characterizing those solvable problems, equivalently, through Turing machines, random access machines, recursive functions and lambda calculus. A full answer to the related question, “How much computational resources are needed for solving a given problem?” is not known today. However, the basic outlines of today’s theory of computational complexity will be presented up to the most famous open problem in computer science, namely the “P = NP” question: if a computer could guess the right answer to a computational problem (and only needs to check its correctness), would that computer be faster than another one that cannot guess the right solution? This may seem a ridiculously obvious case of a clear YES answer, but in fact it is considered by many to be the deepest open question in contemporary mathematics (and computer science, of course).
This module provides the core education in theoretical computer science. The material covered in this module gives students access to any field in computer science, which is based on discrete-mathematical formal foundations, such as the theory of automata and formal languages or compiler design.
Course literature
- Michael Sipser: Introduction to the Theory of Computation,2nd edition, PWS Publishing Company, 1997. (Primary Literature).
- John Hopcroft, Rajeev Motwani, Jeffrey Ullman: Introduction toAutomata Theory, Languages, And Computation, 3rd edition, Pearson, 2006.
Syllabus
- Introduction to Mathematics
- Regular Languages
- Context-free languages
- Turing machines
- Decidability
- Complexiity