Rating: 
Summary: Good book on a difficult subject.
Review: It is difficult to give a good rating to a book on a topic that one finds absolutely despicable. However, I've seen much worse coverage of how computers work from mathematical point of view and this textbook definitely deserves at least 4 on a 1-5 scale.
In a rather understandable way, Mr. Lewis covers subjects ranging from Sets, Relations, and Languages, through Automata, Context-Free Languages, Turing Machines through NP-Completeness. The style of writing is rather dry, but it gets the job done if these are the topics that interest you. I think the best aspect of this book is its small non-intimidating size, allowing the student to think that he or she can actually learn this loathsome stuff.
I recommend it only for classes titled Theory of Computation for this is definitely not a novel to read on your vacation. Good luck, poor students, good luck...
Rating: 
Summary: Not a suitable textbook
Review: After experiencing a semester long course with this book, I have come to the conclusion that this book must be avoided at all costs for Computer Science and possibly even Math majors. The book assumes a significant level of Mathematical background but does attempt to communicate the requirements in the the preface. Also, the book contains numerous errors in definitions and algorithms. Furthermore, these errors tend occur in the introduction of critical concepts. Mathematical proofs are haphazard with inadequate explaination of proof techniques. The book also contains numerous gramatical errors which makes deciphering the book significantly more laborious (ambiguity abounds). Finally, this book attempts the impossible: seperating mathematical concepts from mathematics.
Rating:
Summary: No comparison to Feynman
Review: After reading this book and then reading other comments on this book, I felt compelled to put in my two cents worth. Contrary to another reviewer's opinion, this book is NOTHING like the Feynman lectures. Those books are so well written they can be read and understood by people with no background in physics. This text is complex and elegant in some places, but not something I would really recommend for a beginner (ie. someone unfamiliar with abstract models of computation). If you want a book that conveys the same material in a much more concise and understandable manner, buy the Sipser text.
Rating: 
Summary: Not bad, but certainly could be better
Review: As far as reading the chapters goes, this book is pretty dang good. I think it is written well, and is not to difficult to follow if you have a background in Computer Science (in my school, shout out to Stony Brook, this book is used in a 300 level course). However, the book's examples are to few and far between, and there are no solutions to the problems at the end of each chapter. It's hard to recommend this book as a text for a course, but I think it would make a good supplement. If you are taking a class in theory this could give you some additional insight. But go to the library, don't spend the cash. And also... who the hell is this geek on the cover? It doesn't reveal his identity anywhere in the book. You know this book is bad when they have a herb like him staring at you. This guy needs a new suit, a haircut, and he needs to learn how to smile.
Rating: 
Summary: Recommended for some...
Review: Concerning the FIRST EDITION: (I haven't read the second edition but on flipping through it briefly it appeared watered down) One of the best undergraduate textbooks I had. I would recommend it to anyone interested in math or in approaching computer science from a mathematics perspective. If you dont like abstract mathematics and proofs, or are just interested in writing code for actual, physical computers then you'll hate it. The level of rigor in the book is high for an introductory text, and while there are no specific mathematical prerequisites, you'll need a certain amount of mathematical experience to be able to process it quickly. The style is dry- no history, philosophical musings, or isnt-this-cool hullabaloo -just the facts and a minimum of exposition. Chapter 1 gives the basic discrete math stuff: sets, relations, strings, induction and such. Chapter 2 introduces finite automata (regular languages), a great way to begin careful analysis of computation. Chap 3 covers context-free languages, and is perhaps too long (skim the later sections if you get bored). Chap 4 covers Turing machine basics. Chap 5 gives two alternative formalisms of computation (unrestricted grammars and mu-recursive functions), shows their equivalence with Turing machines, and a construction of a universal turing machine. Chapter 6 is uncomputability and the halting problem. If the earlier chapters seemed a little dull and unmotivated, then things suddenly become very interesting here. Includes an unsolvable tiling problem. Chap 7 is computational complexity and np-completeness. Chap 8 is a solid intro to basic propositional logic. Chap 9 is first-order logic (without equality) and is the weakest chapter in the book. Formal proof systems are not introduced (forgivable considering the length of the book), but the presentation of the Herbrand expansion theorem is hurried, awkward, and confusing. Overall a great book, but you should supplement it with other inexpensive computation theory and logic books. After you've mastered this, check out Papadimitriou's "Computational Complexity" and Hartley Rogers' "Theory of Recursive Functions and Effective Computability", two fantastic intermediate-level books.
Rating:
Summary: Recommended for some...
Review: Concerning the FIRST EDITION: (I haven't read the second edition but on flipping through it briefly it appeared, well, dumbed down) This is one of my favorite undergraduate textbooks. I would recommend it to anyone interested in math or in approaching computer science from a mathematics perspective. If you dont like abstract mathematics and proofs, or are just interested in writing code for actual, physical computers then skip it. That said, this is a great introductory book on computation theory, more rigorous and robust than others I've seen. The mathematical prerequisites are low- all that is needed is familiarity with basic set theory and careful mathematical proofs, but the more "mathematical experience" you have the faster you can read it. The level of rigor in the book is high for an introductory text, without becoming too bogged down (in my opinion). Chapter 2 introduces finite automata (regular languages), a great way to begin careful analysis of computation. Chap 3 covers context-free languages, and is perhaps too long (skim the later sections if you get bored). Chap 4 covers Turing machine basics. Chap 5 gives two alternative formalisms of computation (unrestricted grammars and mu-recursive functions), shows their equivalence with Turing machines, and a construction of a universal turing machine. Chapter 6 is uncomputability and the halting problem. This is where things get really interesting, and all your previous effort is rewarded. Includes an unsolvable tiling problem. Chap 7 is computational complexity and np-completeness. Chaps 8 and 9 develop propositional logic and first-order logic (without equality). I feel introductory logic and computation theory should always be taught together, and this book does a decent job. Unfortunately the presentation of the Herbrand expansion theorem in chap 9 is hurried and awkward, and formal proof systems are not covered. Overall a great book, but it would be a good idea to supplement it with other inexpensive computation theory and logic books. After you've mastered this, check out Papadimitriou's "Computational Complexity" and Hartley Rogers' "Theory of Recursive Functions and Effective Computability", two fantastic intermediate-level books.
Rating:
Summary: A classic text on the theory of computation.
Review: 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.
Rating:
Summary: A classic, but requires good math background
Review: Good book that I am using for a class. The reader needs to be quite comfortable with mathematics to appreciate this book. But overall a very good book on the topic.
Rating:
Summary: A great book on the theory of computation
Review: I am impressed by the book content. I am using this book to teach myself the theory of computation. Computing is a mathematical subject. If you want to appreciate the theory of computation, you must appreciate the value of mathematics. It is a pity there are no answers at the back for self learners
Rating:
Summary: Good books suffer from not being understood!!
Review: I am really surprised sometimes, when I read the reviews about some of the books I have read. Unfortunately, some people lack the required intelligence or background and some probably both to understand such good books and for this reason they give very bad rates. I accept that this is not an easy book, but what I don't accept is to rate a book with 1 star since you couldn't get what it gives. This is one of the best (or at least one of the few) book on theoritical computer science. It is worth to buy it even for the np-completeness chapter that you cannot find anywhere easily. It touches the hardest subjects on this field, and it is of course not an easy book. But with a good undergraduate education on EE, CS, or mathematics, it is not very difficult to grasp the material.
|
