Reus Bernhard. Limits of Computation: From a Programming Perspective

Springer, 2016. — 348 p. — ISBN: 978-3-319-27887-2 ISBN: 978-3-319-27889-6.This textbook discusses the most fundamental and puzzling questions about the foundations of computing. In 23 lecture-sized chapters it provides an exciting tour through the most important results in the field of computability and time complexity, including the Halting Problem, Rice's Theorem, Kleene's Recursion Theorem, the Church-Turing Thesis, Hierarchy Theorems, and Cook-Levin's Theorem. Each chapter contains classroom-tested material, including examples and exercises. Links between adjacent chapters provide a coherent narrative.Fundamental results are explained lucidly by means of programs written in a simple, high-level imperative programming language, which only requires basic mathematical knowledge. Throughout the book, the impact of the presented results on the entire field of computer science is emphasised. Examples range from program analysis to networking, from database programming to popular games and puzzles. Numerous biographical footnotes about the famous scientists who developed the subject are also included.
"Limits of Computation" offers a thorough, yet accessible, introduction to computability and complexity for the computer science student of the 21st century.Computer Science centers on questions about computational problems, and computer programs to solve problems:
What is a computational problem, what is an algorithm, what does it mean to have solved a problem, are some problems unsolvable by any computing device, are there problems intrinsically difficult or impossible to solve automatically, are there problems intrinsically easier to solve than others, …?
How can a machine solve a problem, how to build such a machine, how to specify an algorithm for computer execution, how to design good algorithms, which “language” can a human use to direct the computer, how to design and “debug” programs for computer execution, how to build good programs, …?
Good news: rapid progress has been made in both areas; we stand on the shoulders of giants in both theory and practice. The questions above have many and various answers. The first questions led in mathematical directions to foundational studies: the theories of computability, recursive functions, automata theory and more. The second led in engineering directions: computer architectures, the architectures of programming languages, the art or discipline of programming, software engineering and more.
Since the 1930s our understanding of both areas has developed hand in hand, led by theoreticians such as Kleene, Church, and Gödel; by hardware and software inventors such as Babbage, Von Neumann, and McCarthy; and by Alan Turing’s genius at the borderline between the two areas.This book focuses on the first question area by an approach near the borderline: the theory of computability and complexity (C&C for short) is presented by using a simple programming language. In this language one is able to perform the (many) program constructions needed for the theory. This is done abstractly enough to reveal the great breadth and depth of C&C. Further, it is done concretely and precisely enough to satisfy practice-oriented readers about the constructions’ feasibility. Effect: a reader can see the relative efficiency of the constructions and understand the efficiency of what is constructed.