- Amazon Student members save an additional 10% on Textbooks with promo code TEXTBOOK10. Enter code TEXTBOOK10 at checkout. Here's how (restrictions apply)
Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science Hardcover – Feb 3 1994
|New from||Used from|
Special Offers and Product Promotions
Customers Who Bought This Item Also Bought
No Kindle device required. Download one of the Free Kindle apps to start reading Kindle books on your smartphone, tablet, and computer.
To get the free app, enter your e-mail address or mobile phone number.
"If there is a single book on the theory of computing that should be in every college library collection, this is it. Although written as a text for an advanced undergraduate course in theoretical computer science, the book may serve as an introductory resource, or the foundation for independent study, in many areas of theoretical computing: grammars, automata theory, computability, complexity theory, and unsolvability. The beauty of this book is that the breadth of coverage is complemented with extraordinary depth." -CHOICE
"Theoretical computer science is often viewed as a collection of disparate topics, including computability theory, formal language theory, complexity theory, logic, and so on. This well-written book attempts to unify the subject by introducing each of these topics in turn, then showing how they relate to each other... This is an excellent book that succeeds in tying together a number of areas in theoretical computer science." -COMPUTING REVIEWS
From the Back Cover
This book is a rigorous but readable introduction to some of the central topics in theoretical computer science. The main subjects are computability theory, formal languages, logic and automated deduction, computational complexity (including NP-completeness), and programming language semantics.See all Product Description
Inside This Book(Learn More)
Most Helpful Customer Reviews on Amazon.com (beta)
After a brief review of elementary mathematics and mathematical logic in chapter 1, the authors move right into the consideration of computable functions in chapter 2. They choose a particular abstract programming language in which to study the computability theory, which is built from variables, and programs that can be built from lists of instructions. Examples of programs are given, which have a Fortran flavor, with examples of computing partial functions. Unfortunately, a plethora of GOTO statements appear in the programs, and throughout the rest of the book, which is surprising given the publishing date. The use of these GOTO statements in the book is a major annoyance.
Then in chapter 3, the authors discuss primitive recursive functions, beginning with a treatment of composition, followed by the all-important concept of recursion. The class (PRC) of primitive recursive functions is introduced, and shown to be computable. The primitive recursive predicates are introduced, followed by a proof that the existential and universal quantifiers over an element of a PRC class are also PRC. This is followed by a discussion of minimalization and Godel numbers.
The next chapter is very interesting, wherein the famous halting problem is discussed and related to Church's thesis. The authors stress, most importantly, that an algorithm cannot be defined outside of the choice of a language, and therefore Church's thesis cannot be proved as a theorem. The authors also introduce recursively enumerable sets and show, via diagonalization, that non-recursively enumerable sets exist. They give an interesting example of a function that is computable but not primitive recursive.
The next chapter extends the results to strings of symbols instead of just numbers, and the authors introduce programming languages for doing string computations. One of these is the famous Post-Turing language, which they use to discuss the halting problem, with a variant used in the next chapter on Turing machines. The authors discuss the famous halting problem for Turing machines in this chapter. This is followed in chapter 7 by a discussion of productions and simulation of nondeterministic Turing machines. A very lucid treatment of Post's correspondence problem is given.
Things get somewhat more complicated in chapter 8, where the authors attempt to classify unsolvable problems. It contains one of the best discussions I have seen in the literature on oracles, and the authors give a very clear treatment of arithmetic hierarchies.
The second part of the book reads more like a book on compilers, as the authors delve into the area of grammars and automata. Regular languages, deterministic and non-deterministic finite automata are discussed, and Kleene's theorem, which states that regular languages and finite automata define the same languages, is proven. The context-free languages, so familiar from the study of compilers, are discussed also, along with a proof that a context-free grammar can be reduced to a Chomsky normal form grammar. Pushdown automata, needed for accepting context-free languages, are treated in detail. The authors give a good explanation here as to the additional facilities needed for a finite automaton to decide if a word belongs to a "bracket" language. Chomsky hierarchies are also discussed, and the authors motivate nicely the need for a linear bounded automaton to accept context sensitive languages.
Part three of the book is an overview of mathematical logic, and begins with a treatment of the propositional calculus. The satisfiability problem is discussed for this system, along with how to reduce formulas to normal form. The important compactness theorem is given a very detailed proof. Predicate calculus is then discussed, and Herbrand's theorem, which effectively reduces logical inference in predicate calculus to a problem of satisfiability of universal sentences, is proven. This theorem is fascinating and has important applications to automated theorem proving, as it ties together semantic and syntactical properties of a formal system. The Godel incompleteness theorem and the unsolvability of the satisfiability problem in predicate logic is proven.
In part 4, issues in computational complexity are addressed, the measure of complexity given in terms of the Blum axioms. This is a very abstract way of introducing complexity theory, as it introduces measures of complexity that more general than time and space complexity. The fascinating gap theorem, comparing program performance on two computing machines via complexity measures, is proven. This is followed by a detailed discussion of the speedup theorem, which essentially states that there is a wildly complicated recursive function such that for any program computing this function, there exists another program computing the function that works a lot faster for almost every input. The polynomial-time computability is discussed along with the famous P vs NP problem, with the discussion given in terms of Turing machines. Examples of NP-complete problems are given.
The last part of the book covers semantics, with operational and denotational semantics defined and compared. The emphasis in this part is on programming languages and constructions that one would actually find in practice, and so the preceding chapters on computable functions must be extended. The concept of an approximate ordering is introduced to allow for the instantaneous of a computation at some point before its completion. The denotational semantics of recursion equations and infinitary data structures are discussed, with the latter put it in to deal with the sophisticated systems that are constructed here. The discussion here is very involved, but the authors do a fair job of explaining the need for these types of data structures. The same is done for operational semantics, and the authors finally show that the computable numerical functions are actually partially computable. They then show the existence of computable irrational numbers.
A special note goes to the chapter on Blum's complexity, which is about the only good place where I found it and from where I studied for my course on Complexity I.
For this reason the book requires quite more attention than others, but it really worths all the time one can spend reading it. Truly understanding Computability and Complexity as Professor Davis teaches them with this book is in my opinion a definitely high achievement, bringing the sensation that you grasp it totally, with no space for ambiguity or weakness.