Skip to main content
main-content

About this book

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.

Table of Contents

2016 | OriginalPaper | Chapter

Chapter 1. Limits? What Limits?

Bernhard Reus

Computability

Frontmatter

2016 | OriginalPaper | Chapter

Chapter 2. Problems and Effective Procedures

Bernhard Reus

2016 | OriginalPaper | Chapter

Chapter 3. The WHILE-Language

Bernhard Reus

2016 | OriginalPaper | Chapter

Chapter 4. Semantics of WHILE

Bernhard Reus

2016 | OriginalPaper | Chapter

Chapter 5. Extensions of WHILE

Bernhard Reus

2016 | OriginalPaper | Chapter

Chapter 6. Programs as Data Objects

Bernhard Reus

2016 | OriginalPaper | Chapter

Chapter 7. A Self-interpreter for WHILE

Bernhard Reus

2016 | OriginalPaper | Chapter

Chapter 8. An Undecidable (Non-computable) Problem

Bernhard Reus

2016 | OriginalPaper | Chapter

Chapter 9. More Undecidable Problems

Bernhard Reus

2016 | OriginalPaper | Chapter

Chapter 10. Self-referencing Programs

Bernhard Reus

2016 | OriginalPaper | Chapter

Chapter 11. The Church-Turing Thesis

Bernhard Reus

Complexity

Frontmatter

2016 | OriginalPaper | Chapter

Chapter 12. Measuring Time Usage

Bernhard Reus

2016 | OriginalPaper | Chapter

Chapter 13. Complexity Classes

Bernhard Reus

2016 | OriginalPaper | Chapter

Chapter 14. Robustness of P

Bernhard Reus

2016 | OriginalPaper | Chapter

Chapter 15. Hierarchy Theorems

Bernhard Reus

2016 | OriginalPaper | Chapter

Chapter 16. Famous Problems in P

Bernhard Reus

2016 | OriginalPaper | Chapter

Chapter 17. Common Problems Not Known to Be in P

Bernhard Reus

2016 | OriginalPaper | Chapter

Chapter 18. The One-Million-Dollar Question

Bernhard Reus

2016 | OriginalPaper | Chapter

Chapter 19. How Hard Is a Problem?

Bernhard Reus

2016 | OriginalPaper | Chapter

Chapter 20. Complete Problems

Bernhard Reus

2016 | OriginalPaper | Chapter

Chapter 21. How to Solve NP-Complete Problems

Bernhard Reus

2016 | OriginalPaper | Chapter

Chapter 22. Molecular Computing

Bernhard Reus

2016 | OriginalPaper | Chapter

Chapter 23. Quantum Computing

Bernhard Reus
Additional information