DeepRead
Cover of Theory of computation

Theory of computation

Michael Sipser · 2007

Mathematics and physics › Feynman and physics

#2,265 most recommended

About the book

An undergraduate-level introduction to the theory of computation, covering formal models of computing and what they can and cannot do. It spans finite automata and regular languages, context-free grammars and pushdown automata, Turing machines, decidability, and time and space complexity, including NP-completeness. Rather than advancing a single thesis, the book builds a hierarchy of computational models and uses it to map the limits of computation. Its central claims are that each model class recognizes a precisely characterized set of languages, that some problems, such as the halting problem, cannot be solved by any algorithm, and that resource-bounded classes such as P and NP give a principled way to separate tractable problems from apparently intractable ones. Proofs are presented as the main vehicle for these claims.

Written by Claude from what it knows of this book.

What Hacker News says 74% recommend · 0% critical

024200820102015202020242019 peak · 4
This bookAverage book in Feynman and physics

In the commenters’ own words

What Open Library readers say

No Open Library reader has rated it yet.

  • 4 want to read
  • 0 reading
  • 0 have read

Open Library’s page for the book

What critics say, via Wikipedia

No Wikipedia article about this book yet, so no critics to quote.

Reddit communities — coming later

The threads it came up in

Details

First published
2007
Editions known
2 at Open Library
Open Library
OL18180546W

Computational complexityMachine theory

Explore in the mosaic

Read next: its neighbours on the mosaic