Computers Ltd.

This book provides a brief introduction to the concept of algorithms before discussing the limitations of computation. Specifically, Harel explains undecidable problems (that is, problems for which no algorithm exists) and infeasible problems (that is, problems for which only algorithms are known that have an exponential runtime). I like this book (and its splendid title) because of its focus on the limitations of computation. Harel does a marvelous job in explaining two difficult topics about computation. The understanding of any scientific discipline requires the understanding of its limits, and the limits of computation are as significant as they are surprising.

Turing’s great contributions, arguably the most important scientific contributions of the last century, are universality (all computers have the same power) and computability (there are limitations on that power—problems that cannot be solved). Harel does an outstanding job of explaining these and related concepts in layman’s terms.

Learning Turing’s results from the original paper (as I had to do in that 1966 class) requires sophistication and experience in mathematics, as it is couched in mathematical notation that can be impenetrable. But one of the amazing outgrowths of Turing’s concept of universality is that we can choose to express it in… show more.