About this course

This course serves to introduce the theoretical and mathematical ideas behind computation. It starts by studying simple models of computation (Finite automata) where we learn how to rigorously argue about what problems can be solved by them (Regular languages) and what cannot be solved by them and how to prove it (Pumping lemma). We proceed to understand more powerful models (Push down machines, Turing machines) and learn how to mathematically argue their computational powers and limitations.

The central take away from this course is the ability to mathematically formulate what can be computed and what cannot be, for various computational models. En-route, we will also learn several methods and tools that help us do this.

Towards the end, we will try to see resource bounded computation and several questions about the nature of computation in the resource bounded setting.