Elements of the Theory of Computation (2nd Edition) (Paperback)

by Harry Lewis (Author), Christos H. Papadimitriou (Author)

Editorial Reviews

Product Description
Lewis and Papadimitriou present this long awaited Second Edition of their best-selling theory of computation. The authors are well-known for their clear presentation that makes the material accessible to a a broad audience and requires no special previous mathematical experience. In this new edition, the authors incorporate a somewhat more informal, friendly writing style to present both classical and contemporary theories of computation. Algorithms, complexity analysis, and algorithmic ideas are introduced informally in Chapter 1, and are pursued throughout the book. Each section is followed by problems.

From the Publisher
A general, yet comprehensive, introduction to the classical and contemporary theory of computation. --This text refers to an out of print or unavailable edition of this title.

See all Editorial Reviews

Product Details

• Paperback: 361 pages
• Publisher: Prentice Hall; 2 edition (August 17, 1997)
• Language: English
• ISBN-10: 0132624788
• ISBN-13: 978-0132624787
• Product Dimensions: 9.6 x 7.2 x 0.8 inches
• Shipping Weight: 1.6 pounds (View shipping rates and policies)
• Average Customer Review: 2.8 out of 5 stars See all reviews (34 customer reviews)
• Amazon.com Sales Rank: #599,503 in Books (See Bestsellers in Books)

Customer Reviews

Most Helpful Customer Reviews

21 of 22 people found the following review helpful:

4.0 out of 5 stars An Amazing Book on tough topic, November 20, 2001

By	Sean Francisco Smith "New York Jazz MythMaker" (Brooklyn, NY United States) - See all my reviews (REAL NAME)

This was one of my favorite textbooks from college. In fact, I still have it on my shelf. It is a fantastic textbook, attemtping to introduce the Theoretical Foundations of Computer Science, in essence the science. In covering this, it moves into topics such as Finite Automata, Parsing, and Turing Machines.

I feel the negative reviews are due to some confusion. This is not an algorithms book, or a programming book, or an "intro to AI" book. It's a Math textbook. It's language is one of theorems and proofs, and this would be hard going for someone not comfortable with a college-level abstract mathematics background.

For those of you who have such a background, this book covers a topic where mathematics can become elegant. A physics major friend of mine fell in love with it, and he had no interest in Comp Sci!!

For it's topic, a similar book would be Feynman's lecture notes on Physics. Both those volumes and this book were attempt to bring the highest levels of theory within the field to the undergraduate audience. Both succeed.

9 of 9 people found the following review helpful:

5.0 out of 5 stars You'll love it or hate it., September 20, 2003

By	Jason T (Canada) - See all my reviews

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 a class and they absolutely despise it. But a small number of people like me loved it, in fact its still one of my favorite textbooks. I first learned automata and computation theory here (which explains some of my fondness for the book), and it seemed kind of dull and strange until about halfway through- at which point I realized it's all very cool and I subsequently poured over the entire book several times. To get through it you need to enjoy mathematics and careful, rigorous definitions and proofs- rather than viewing these things as pointless obscurantism or pedantic arrogance. Engineering students tend to find the book dense, 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 you'll appreciate the extra rigor and precision (compared to most computation theory books). There are a few rough spots in it (I admit the development of the Herbrand expansion theorem in the last chapter is a mess, and the coverage of parsing theory isn't great), and some of the terminology and approaches are a little nonstandard, 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 second edition has removed the chapters on logic, and I've heard its watered down. If you want something a little harder and more pure-math oriented, try Martin Davis's Computability and Unsolvability.

5 of 5 people found the following review helpful:

5.0 out of 5 stars A good textbook, April 24, 2005

By	Jill Malter ([e-mail]) - See all my reviews (TOP 500 REVIEWER)

I taught a couple of classes from the first edition of this textbook, and my students did fairly well. On the whole, they were able to understand the material and solve the homework problems. I certainly wouldn't mind teaching a class on this subject from the second edition as well, which I feel is a mild improvement over the first one.

The chapter on finite automata is excellent. And the material on context-free languages is thorough and well written. So is the introduction to Turing machines.

Of course, the book then spends a fair amount of time on recursive function theory. That is exactly what I want it to do. And I think the chapter on unsolvability, starting with the Halting Problem, is excellent.

The style, especially of the first edition, is a little formal. But this is serious mathematical material, and I think it is not asking too much to require students to handle this subject in such a manner.