Elements of the Theory of Computation

by Christos H. Papadimitriou and Harry R. Lewis

Book Overview

A general, yet comprehensive, introduction to the classical and contemporary theory of computation.

• Format: Hardcover
• Language: English
• ISBN: 0132734176
• ISBN13: 9780132734172
• Release Date: January 1981
• Publisher: Prentice Hall
• Length: 496 Pages
• Weight: 1.78 lbs.

Customer Reviews

The most understandable book on computation theory I have used

Approximately two decades ago, I developed a course in the theory of computation for undergraduates. The coverage was finite automata, context-free languages, Turing machines and computational complexity. This was the text that I used and I have never regretted it and neither did the students. They found it to be very understandable, they were generally able to read and follow the proofs. Over the years, I left teaching and have recently come back to it. After using other texts for a course in computation theory in the last few years, next academic year I am going to return to this one. One of the greatest strengths is the simple form of notation, when using other textbooks I have often said something equivalent to, "I am puzzled why the author used this form of notation for this operation." I have never said that when using this book. The examples are crisp, there are many diagrams and a large number of exercises are included at the ends of the chapters.

A good textbook

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.

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 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.

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.

At least the old edition of this book is great

The other reviewers seem to agree in that this book is not to be recommended. I don't know the edition that is reviewed here (I browsed through it once and it seems to be heavily abridged compared to the old edition).The older edition is considered by me and most of my fellow students one of the best books on the matter (if not the best).Keep in mind that it is a book about the THEROTICAL foundations of computer science and not a programming or algorithm text book for beginners. Of course all the basic proofs of "long known" theorems have to be explained...Since I don't know how the undergraduate maths knowledge in the US is, I can't say if the explanations presented in this book are suitable for US undergraduates.I however (and I'm by far no maths genius) had no problems in understanding everything when I read the book starting with page one. I used the book as the only preparation material for my undergraduate examination on the subject--although our professor did use another book during his lecture--and I don't regret it.I strongly recommend the book to everyone with a serious interest in theoretical CS, but try to get the old edition (paperback has a red cover, hardcover has a brown cover, the format is slighty larger than A5 papersize).