What do you think?
Rate this book
Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science
This introductory text 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 tripled.
* Automata theory, computational logic, and complexity theory are presented in a flexible manner, and can be covered in a variety of different arrangements.
* 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 tripled.
* Automata theory, computational logic, and complexity theory are presented in a flexible manner, and can be covered in a variety of different arrangements.
609 pages, Kindle Edition
First published January 1, 1983
12 people are currently reading
173 people want to read
About the author
Martin D. Davis
19 books13 followersMartin David Davis (born 1928) is Professor Emeritus at New York University's Computer Science Department.
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 - 2 of 2 reviews
April 4, 2021
Amazon Review
I regret not reading this book earlier
This book contains all the foundational information that you may need to understand theoretical computer science. The book not only presents but also proves the most relevant form of computations. Using those forms of computations, the authors prove several relevant theorems in computer science (e.g. Rice theorem, impossibility of the halting problem, Godel incompleteness theorem for predicate calculus, Cook's theorem, etc). All the theorems are well motivated and presented during the right time.
I'd recommend this book to anyone interested in the theory of computability. Indeed, the book covers so many topics that you'd probably need 3 or 4 books to get the same material.
Pedro Andres Rangel Walteros
---
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
---
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.
I regret not reading this book earlier
This book contains all the foundational information that you may need to understand theoretical computer science. The book not only presents but also proves the most relevant form of computations. Using those forms of computations, the authors prove several relevant theorems in computer science (e.g. Rice theorem, impossibility of the halting problem, Godel incompleteness theorem for predicate calculus, Cook's theorem, etc). All the theorems are well motivated and presented during the right time.
I'd recommend this book to anyone interested in the theory of computability. Indeed, the book covers so many topics that you'd probably need 3 or 4 books to get the same material.
Pedro Andres Rangel Walteros
---
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
---
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.
Read
March 31, 2012good book
Displaying 1 - 2 of 2 reviews