Sipser Michael. Introduction to The Theory of Computation

Second Edition. — Thomson Course Technology, 2006. — xx+432 p. — ISBN 0-534-95097-3.This highly anticipated revision of Michael Sipser's popular text builds upon the strengths of the previous edition. It tells the fascinating story of the theory of computation-a subject with beautiful results and exciting unsolved questions at the crossroads of mathematics and computer science. Sipser's candid, crystal-clear style allows students at every level to understand and enjoy this field. His innovative II proof idea" sections reveal the intuition underpinning the formal proofs of theorems by explaining profound concepts in plain English.
The new edition incorporates many improvements students and professors have suggested over the years and offers completely updated, classroom-tested problem sets with sample solutions at the end of each chapter.Welcome!
You are about to embark on the study of a fascinating and important subject the theory of computation. It comprises the fundamental mathematical properties of computer hardware, software, and certain applications thereof. In studying this subject we seek to determine what can and cannot be computed, how quickly, with how much memory, and on which type of computational model. The subject has obvious connections with engineering practice, and, as in many sciences, it also has purely philosophical aspects.
Part One: Automata and Languages.
Regular Languages.
Context-Free Languages.
Part Two: Computability Theory.
The Church-Turing Thesis.
Decidability.
Reducibility.
Advanced Topics in Computability Theory.
Part Three: Complexity Theory.
Time Complexity.
Space Complexity.
Intractability.
Advanced topics in complexity theory.