DeepRead
Cover of Computability and complexity

Computability and complexity

Neil D. Jones · 1997

Programming and computer science › Algorithms and coding interviews

#15,712 most recommended

About the book

A graduate-level introduction to the theory of computation: what can be computed in principle (computability, including undecidability and recursion theorems) and what can be computed efficiently (time and space complexity classes, including NP-completeness). It covers both halves of the field in one text, with the material framed around programs and programming languages. The book argues that computability and complexity theory are best taught from a programming perspective, treating programs, interpreters and program transformations as the main objects of study instead of relying mainly on abstract machine models. On this view, classical results such as the undecidability of the halting problem, Rice's theorem and the hierarchy theorems follow naturally from properties of programs and the languages they are written in. It presents this approach as a more accessible route into the field for working programmers.

Written by Claude from what it knows of this book.

What Hacker News says 50% recommend · 0% critical

02420152016201720182015 peak · 1
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

Details

First published
1997
ISBN
9780585037028
Editions known
4 at Open Library
Open Library
OL3343883W

Computational complexityComputer programmingElectronic digital computersProgramming

Explore in the mosaic

Read next: its neighbours on the mosaic