Introduction to Computer Theory [Paperback]

Daniel I. A. Cohen (Author)

Book Description

Publication Date: October 25, 1996 | ISBN-10: 0471137723 | ISBN-13: 978-0471137726 | Edition: 2

This text strikes a good balance between rigor and an intuitive approach to computer theory. Covers all the topics needed by computer scientists with a sometimes humorous approach that reviewers found "refreshing". It is easy to read and the coverage of mathematics is fairly simple so readers do not have to worry about proving theorems.

Product Details

• Paperback: 634 pages
• Publisher: Wiley; 2 edition (October 25, 1996)
• Language: English
• ISBN-10: 0471137723
• ISBN-13: 978-0471137726
• Product Dimensions: 10.1 x 7.3 x 1.7 inches
• Shipping Weight: 3.1 pounds (View shipping rates and policies)
• Average Customer Review: 4.7 out of 5 stars  See all reviews (10 customer reviews)
• Amazon Best Sellers Rank: #492,706 in Books (See Top 100 in Books)
  • #78 in Books > Computers & Technology > Computer Science > Artificial Intelligence > Theory of Computing

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

17 of 17 people found the following review helpful:

4.0 out of 5 stars Excellent, Accessible Book, September 28, 2005

By 

David A. Lessnau (USA) - See all my reviews
(REAL NAME)   

This review is from: Introduction to Computer Theory (Paperback)

This an excellent book. Basically, the whole point of it is to mathematically define what a computer is and prove that it works. The author does this by defining and manipulating mathematical alphabets and languages without resorting to any kind of advanced math. Starting from nothing, the whole thing leads up to Turing Machines. More specifically, according to the Preface, the goals of the book are:

"(1) to introduce a student of Computer Science to the need for and the working of mathematical proof; (2) to develop facility with the concepts, notations, and techniques of the theories of Automata, Formal Languages, and Turing machines; and (3) to provide historical perspective on the creation of the computer with a profound understanding of some of its capabilities and limitations."

The author did a wonderful job of it. Plus, unlike almost all other computer/math books I've read, this book is almost enjoyable to read. Again, as stated in the Preface:

"This book is written for students with no presumed background of any kind. Every mathematical concept used is introduced from scratch. Extensive examples and illustrations spell out everything in detail to avoid any possibility of confusion."

Astonishingly, those are all true statements. At a guess, I'd say that almost anyone interested in computers could get through this book without undue stress. To make it more meaningful, I'd suggest (only suggest) prerequisites of having programmed a computer and knowing some discrete math. From that point of view, it's odd that as of last year, this book was used in Florida State University's (FSU's) COT 4420: "Theory of Computation" course, which, obviously, is a 4000 level course requiring various prerequisites that put it out of the reach of all but senior (or graduate) level students.

Now, with all that glowing out of the way, there are a couple of small problems with the book. The first is simply that the exercises don't have any solutions. For the self-studyer, that's a bad thing. In a school teaching environment, it's probably acceptable, though. The second problem is that after getting through the book, I simply have to ask: "So what? WHY should I learn this?" Again, in the Preface, the author states:

"Leaving aside the obvious worth of knowledge for its own sake, the terminology, notations, and techniques of Computer Theory are necessary in the teaching of courses on computer design, Artificial Intelligence, the analysis of algorithms, and so forth. Of all the programming skills undergraduate students learn, two of the most important are the abilities to recognize and manipulate context-free grammars and to understand the power of the recursive interaction of parts of a procedure. Very little can be accomplished if each advanced course has to begin at the level of defining rules of production and derivations."

But, in my experience, I have to say that except for one reference in one other book I've read, I've never seen any of this stuff used. Even more, I've never known anyone who even knew of anyone who used (or even knew of) any of it. EVERYTHING has been done at a much higher level of abstraction than alphabets, languages, and various levels of algorithms and machines up to Turing Machines. I'm not saying that the material in this book isn't used SOMEWHERE. But, I'd honestly have liked to have seen actual, specific, concrete cases: they'd be fascinating.

So, factoring those two nits in, I rate this book at 4 stars out of 5. If those two things don't bother you, then you could easily consider this a 5 star book.

11 of 11 people found the following review helpful:

5.0 out of 5 stars Great companion to Aho and Ullman's book, August 25, 1999

By A Customer

This review is from: Introduction to Computer Theory (Paperback)

This book is great. It gives a completely different approach to atomata theory and computability than Aho and Ullman's book. The the latter has demostrations from an algebraic point of view, the former gives constructive demostrations which are usually more understandable to me. This is a great introduction to computer theory and I would recommend it instead of Aho's book as a first encounter with these themes.

14 of 15 people found the following review helpful:

5.0 out of 5 stars Great Book!, June 4, 2001

By 

Christoffer (Raleigh, NC) - See all my reviews

This review is from: Introduction to Computer Theory (Paperback)

This is a great book. I read the first edition many years ago, and it too was great. Everything is explained in order, and explained well - it is very accessable, even to the casual reader interested in the topics presented. It was through this book that I was able to actually write software that demonstrated Kleene's Theorem, (RE=NFA=DFA) converting between Regular Expressions, NFA's and DFA's.

Unlike many textbooks, reading this one is actually FUN. By the time I was done, I felt that I understood everything that was presented. That's how good this text is.

// CHRIS (Darien, Connecticut)