|
Elements of the Theory of Computation (2nd Edition)
 |
Author: Harry R. Lewis, Christos H. Papadimitriou
List Price: $87.00
Our Price: Click to see the latest and low price
ISBN: 0132624788
Publisher: Prentice Hall (07 August, 1997)
Edition: Hardcover
Sales Rank: 158,653
Average Customer Rating: 2.93 out of 5
|
Customer ReviewsRating: 2 out of 5
A reference at best, a textbook from hell
I took a Theory of Computation class with Harry Lewis, one of the book's author this last semester at Harvard. Lewis may be a gifted professor, but if you are looking for a textbook, look for something else (Sipser would be a much better idea). It is impossible to learn from this book; the examples are too complex, the questions are outlandishly difficult. I got my A but it was not thanks to this book. Steer clear.
Rating: 5 out of 5
You'll love it or hate it.
I discuss the first edition, I havent read the updated version. People have strong opinions about this classic book. Many students have it forced upon them for some class and they absolutely despise it. But a small number of people like me loved it, in fact its one of the best textbooks I own. To get through it you need to enjoy mathematics and careful, rigorous definitions and proofs- rather than viewing these things as pointless obscuring or pedantic arrogance. Engineering students tend to find the book tedious, boring, and too difficult. Some people are intimidated by the sheer volume of special notation used. But if you're inclined towards mathematics or theoretical work I think you'll enjoy the extra rigor and precision (compared to most computation theory books). There are a few rough spots in it but overall a great book that will give you the foundation to begin studying computational complexity theory, recursive function theory, or mathematical logic. Note that the 2cd edition has unfortunately removed the chapters on logic, and I've heard its a little watered down, so be careful choosing which one you want.
Rating: 5 out of 5
A classic text on the theory of computation.
Elements of the Theory of Computation, by Lewis and Papadimitriou, is something of a classic in the theory of computation. Of the many books I have used to teach the theory of computation, this is the one I have been most satisfied with. It covers all of the fundamental concepts one would expect in such a book (more on this below) but offers a bit more mathematical rigor than most other books I've seen on this topic. It also covers one topic that is rarely even mentioned in other textbooks: the composition of Turing machines.The book begins with a brief introduction to the relevant discrete mathematics (such as set theory and cardinality) and proof techniques, then introduces the concepts of finite automata, regular expressions, and regular languages, describing their interrelationships. It proceeds to context-free languages, pushdown automata, parse trees, pumping lemmas, Turing machines, undecidability, computational complexity, and the theory of NP-completeness. (These are all standard topics.) Along the way, Lewis and Papadimitriou also introduce random access Turing machines and recursive functions, and do a nice job of explaining the halting problem and how this translates into undecidable problems involving grammars, various questions about Turing machines, and even two-dimensional tiling problems. All of these topics are covered with an appropriate mix of formalism and intuition. Perhaps the feature I like best is the discussion of composing simple Turing machines to obtain more complex and interesting machines. The authors even introduce a convenient graphical notation for combining Turing machines and spell out specific rules for composition. While most authors are forced to immediately employ heuristics in reasoning about complex Turing machines (lest the notation become overwhelming), Lewis and Papadimitriou are able to keep the discussion more formal and structured by virtue of their Turing machine "schema". I believe this makes their arguments more rigorous and even easier to follow. This is clearly one of the best books on the theory of computation. However, be aware that there have been very significant changes from the first edition, which was lengthier and more thorough. I confess that I actually prefer the first edition, as it contains nice sections on logic and predicate calculus (which have been removed from the 2nd edition), and is a bit more formal (albeit with some fairly awful notation). The 2nd edition is definitely crisper, with much cleaner notation; it is clearly more student-friendly, which was presumably the aim of the new edition. If you wish to teach an introduction to theoretical computer science, or wish to learn it on your own, this would be a fine book to use. It's hard to go wrong with this classic.
Similar Products
· Introduction to Algorithms: A Creative Approach
· Computers and Intractability: A Guide to the Theory of Np-Completeness (Series of Books in the Mathematical Sciences)
· Introduction to the Theory of Computation
· Introduction to Algorithms, Second Edition
· Introduction to Automata Theory, Languages, and Computation (2nd Edition)
|
