Customer Reviews

Computability and Complexity Theory (Texts in Computer Science)

5 star:		(2)
4 star:		(1)
3 star:		(2)
2 star:		(2)
1 star:		(3)

 

 

It's rather disappointing that many universities use this textbook in courses on the subject matter. While it does cover some inseresting and important things, in general the book is terribly written. The back cover states that this text assumes no prerequisites - nothing could be further from the truth. The first chapter purports to provides all prerequisites needed, but it is poorly done and insufficient. Both the first chapter and all subsequent chapters make use of mathematical and computational symbols and terminology that are not explained. Even if you're generally familiar with them, you'll still have to look up the exact definitions in another book. Most of the text in the book is written in a terribly confusing manner that requires it to be re-read multiple times. The proofs are the same way (I have seen some of these proofs written in a very clear manner elsewhere). The authors even omit some proofs because they're "obvious" (although I have been confronted with having to come up with these proofs on graduate-level exams). Possibly the most frustrating thing about this book is the fact that frequently (usually when introducting a new topic) it will give a tiny bit of background and then throw out a few homework problems. Instead of explaining what's going on, the authors decide to let these homework problems take the place of a few pages of definitions, explanations, and examples (note that there are no solutions to the hw problems in the book). Not only will you struggle with the rest of the material if you can't get those problems, but it makes it nearly impossible to merely read the book.

I found this one disapointing. For example, they do a nice job very carefully and clearly distinguishing "decidable" and "acceptable" languages. Then they talk about languages Turing machines "recognize" without saying if these are acceptable or decidable or what. This kind of thing is frustrating. That said, I did learn things from this book. Many things are well covered. But if you buy one book, buy Sipser instead.

I bought this textbook for my class of Theory of Computation. It is a really hard class, and the material is really difficult to understand, especially when you are new to it. The textbook did not help me at all to understand the course. It is a small textbook, not clear enough, and I think expensive for what it is.

In this case, the point to take home is how to not write a book. This book does the worst job of explaining concepts in computability and complexity theory. There is no intuition given behind any of the proofs. Moreover, the language is so bad (I mean way beyond being terse) that most of the times it takes longer to read than it would take to read from another decently written undergraduate text on the same topic/proof. Most of the proofs start with "It is obvious" when it is far from it. It is really sad that such a beautiful subject is treated in such a manner. It is even more sad (and surprising) to see that it is used as the main textbook in a course on complexity theory. I would recommend reading from Sipser or Papadimitriou.

There is zero formatting in this text - it looks like its just popped right out of latex and it is hard to read. Variables are defined early on in the book and then referenced 50 pages later and you have no idea what they are talking about. The overall organization is horrible and the writing is horrible. I ask that you don't buy it new if you need it for school simply because you'll regret supporting the author for this terrible thing.

For an attempt to lay out the foundations of computability theory, this book falls short. The first problem is the poor typography. For example, Definition 1.7 on page 11 consists of a list of axioms A1, A2, ... A9, but A8 and A9 actually refer to different terms than A1 through A7, and the text that is supposed to indicate this is hard to see because of awkward indentation. This is one example, and countless similar problems throughout the book make it hard to read but easy to misunderstand.

The second problem is poor notation and careless omissions. Important terms are casually defined in the middle of paragraphs, and notation is used inconsistently. Theorems, definitions, propositions, and homework problems each have their own numbering system, so finding the right page can be very irritating. Worst of all, instead of taking the definitions and theorems as written, you have to figure out what the authors intended to say.

If this book is intended to be rigorous, it fails because there are too many cut corners. If it is intended to be interesting, then it fails because the writing isn't engaging. If it is intended to be a good reference, then it fails because the index is incomplete and the organization is poor. I just can't think of any way to look at this book as a success at anything.

Computability and Complexity Theory (Texts in Computer Science)
This book is dense, in the sense that there is a lot of information explained using very few words, which means you have to do some thinking to get anything out of it. You have to make sure you have a firm grasp on each concept before you go on, because they just keep building on each other. There's nothing necessarily bad about the book; but for the purpose of the class that I read the book for, it could have offered a little more by way of explanation and reminders, to help the student learn and understand what it was talking about.

Because of the price I bought a used book. The new book costs $90 and this used-like new one costs only $9. It's really like new and I'm very satisfied with that.

Couldn't they have explained just a little more? I find this book maddening as I try to deciper sometimes cryptic assertions. And once I get stuck it seems I have nowhere to turn. It's not like the local library carries texts on this subject so there's not much easily available for me to supplement this book with, so I'm left to stare at the page for 3 days until I figure it out.

This book is aimed as an introductory text book on computer science theory. The book is suited for both undergraduate and graduate studies.
I would have never expected a book of only a few pages to cover computability and complexity theory basics from introductory undergraduate to early graduate levels. This is because, the author focusses only on core concepts and strives to make them as clear and concise as possible using the power of the mathematical language. It explains the hard theory and logic by easy sentences and words. Even if you use English as foreign language you can read this book by yourself and understand its contents easily having a good background on mathematical language and mathematical thought.