Instructor: Prof. Somenath Biswas, Department of Computer Science and Engineering, IIT Kanpur.
The objective of the course is to provide an exposition first to the notion of computability, then to the notion of computational feasibility or tractability. We first convince ourselves that for our purpose it suffices to consider only language recognition problems instead of general computational problems. We then provide a thorough account of finite-state automata and regular languages, not only because these capture the simplest language class of interest and are useful in many diverse domains. We then consider context grammars and languages, and their properties. Next, we consider Turing machines (TMs). We then obtain the separation of the classes recursively enumerable, and recursive. A number of TM-related problems are shown to be undecidable. Finally, we introduce the notion of feasible or tractable computation.
