Theory of Computation

Code: MA352 | L-T-P-C: 3-0-0-6

Prerequisites: MA 252 MA 351

Computability theory: Turing machines, combination of Turing machines, Turing acceptable and decidable languages, computable functions, algorithms, Church-Turing thesis, grammatically computable functions, µ-recursive functions, lambda calculus, decidability, decidable problems concerning regular and context-free languages, halting problem, Rice's theorem, Post's correspondence problem, undecidable problems from language theory via reducibility, the recursion theorem, Turing reducibility; Computational theory: computational complexity, time and space bounded computations, time and space hierarchies, relations among complexity measures, classes P and NP; reducibilities, NP-compleness.

Texts:

1. H. R. Lewis and C. H. Papadimitriou, Elements of the Theory of Computation, Prentice Hall of India, 1997.
2. J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Narosa, 1979.
3. M. Sipser, Introduction to the Theory of Computation, Thomson Asia, 1997.

References:

1. D. Kozen, Theory of Computation, Springer, 2006.
2. D. S. Garey and G. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979.
3. C. H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
4. J. L. Balcazar, J. Diaz and J. Gabarro, Structural Complexity, Vol 1, 2nd Edition, Springer-Verlag, 1995.
5. E. Mendelson, Introduction to Mathematical Logic, Wadsworth & Brooks, 1987.