Computability, Complexity, and Languages is an introductory text that covers the key areas of computer science, including recursive function theory, formal languages, and automata. It assumes a minimal background in formal mathematics. The book is divided into five parts: Computability, Grammars and Automata, Logic, Complexity, and Unsolvability.

• Computability theory is introduced in a manner that makes maximum use of previous programming experience, including a "universal" program that takes up less than a page.
• The number of exercises included has more than...

Computers are everywhere today--at work, in the bank, in artist's studios, sometimes even in our pockets--yet they remain to many of us objects of irreducible mystery. How can today's computers perform such a bewildering variety of tasks if computing is just glorified arithmetic? The answer, as Martin Davis lucidly illustrates, lies in the fact that computers are essentially engines of logic. Their hardware and software embody concepts developed over centuries by logicians such as Leibniz, Boole, and Godel, culminating in the amazing insights of Alan Turing. The Universal Computer traces the...

In this classic text, Dr. Davis provides a clear introduction to computability, at an advanced undergraduate level, that serves the needs of specialists and non-specialists alike.
In Part One (Chapters 1-5), Professor Davis outlines the general theory of computability, discussing such topics as computable functions, operations on computable functions, recursive functions, Turing machines, self-applied, and unsolvable decision problems. The author has been careful, especially in the first seven chapters, to assume no special mathematical training on the part of the reader.
Part Two...