17CS54
AUTOMATA THEORY AND COMPUTABILITY
[As per Choice Based Credit System (CBCS) scheme]
(Effective from the academic year 2017-2018)
SEMESTER - V

This Page Provides Information ABOUT AUTOMATA THEORY AND COMPUTABILITY - ATC Module 1
Variants of Turing Machines (TM),The model of Line ar Bounded automata, Decidability, Definition of an algorithm, decidability, decidable languages, Undecidable languages, halting problem of TM, Post correspondence problem, Complexity, Growth rate of functions, the classes of P and NP, Quantum Computation, quantum computers, Church-Turing thesis

TEXT BOOK MODULE WISE
1. Elaine Rich, Automata, Computability and Complexity, 1st Edition, Pearson Education,2012/2013
2. K L P Mishra, N Chandrasekaran , 3rd Edition, Theory of Computer Science, PhI, 2012