Objectives. The objective of the Theory of Computing course is to introduce and study abstract, mathematical models of computation (such as finite state machines, push down machines, and Turing machines), and to use the abstract machine models to study the ability to solve computational problems, by identifying both the intrinsic limitations of computing devices, and the practical limitations due to limited availability of resources (time and space). A second objective is to show how to reason and prove properties about computing in a precise, formal, abstract way.
Prerequisites. There are no prerequisites in terms of courses to attend. Students should be familiar with notions of mathematics and set theory, and with basic proof techniques, as taught in the mathematics courses of a bachelor in computer science.
Teaching material
[M1] Introduction to Automata Theory, Languages, and Computation (2nd edition). J.E. Hopcroft, R. Motwani, J.D. Ullman. Addison Wesley, 2003.Further reading material
[M2] Lecture Notes for Theory of Computing. Diego Calvanese. 2004. Available on the course web page as scanned pages in pdf.
teaching page of Diego Calvanese