Theory of Computation
R. Inkulu at cse.iitg in Spring 2012


Overview      [Sip]: 1-3

Introduction The Church-Turing Thesis The Chomsky Hierarchy More on Undecidability Intro to Complexity Classes Polynomial Time Polynomial Space Randomized computation      [AB]: 123-139; [note]

Conclusions


* [HU]: Introduction to Automata Theory, Languages, and Computation by John E Hopcroft and Jeffrey D. Ullman, First Edition.
* [Sip]: Introduction to the Theory of Computation by Michael Sipser, First Edition.

* [AB]: Computational Complexity by Sanjeev Arora and Boaz Barak, First Edition.