DeepRead
Cover of Elements of the Theory of Computation

Elements of the Theory of Computation

Lewis, Harry R., and Christos H. Papadimitriou · 1981

Programming and computer science › Algorithms and coding interviews

#6,031 most recommended

About the book

A textbook on the formal foundations of computation. It covers finite automata and regular languages, context-free grammars and pushdown automata, Turing machines and the Church-Turing thesis, and the distinction between what machines can and cannot decide. It also introduces computational complexity, including time and space bounds and the classes P and NP. The book's central claim is that a few precise mathematical models, from finite automata up to Turing machines, capture the essential behaviour of computation, and that questions about them can be answered rigorously. It presents these models as a hierarchy of increasing power and uses proof techniques such as diagonalization and reduction to establish both what is computable and what is undecidable. It then argues that computability alone is not enough, and that the resources needed to solve a problem, and the NP-complete problems in particular, are the next thing to analyse formally.

Written by Claude from what it knows of this book.

What Hacker News says 83% recommend · 0% critical

02420072010201520192009 peak · 2
This bookAverage book in Algorithms and coding interviews

In the commenters’ own words

What Open Library readers say

No Open Library reader has rated it yet.

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
1981
ISBN
9780132734172
Editions known
2 at Open Library
Open Library
OL34834662W

Explore in the mosaic

Read next: its neighbours on the mosaic