Limits of Computation

Foreword.- Limits? What Limits?.- Part I Computability.- Problems and Effective Procedures.- The WHILE-Language.- Semantics of WHILE.- Extensions of WHILE.- Programs As Data Objects.- A Self-Interpreter for WHILE.- An Undecidable (Non-computable) Problem.- More Undecidable Problems.- Self-referencing Programs.- The Church-Turing Thesis.- Part II Complexity.- Measuring Time Usage.- Complexity Classes.- Robustness of P.- Hierarchy Theorems.- Famous Problems in P.- Common Problems not Known to be in P.- The One-Million-Dollar Question.- How Hard is a Problem?.- Complete Problems.- How to Solve NP-complete Problems?.- Part III Emerging New Models of Computation - "going nano".- Molecular Computing.- Quantum Computing.- Appendix A: Further Reading - Computability and Complexity Textbooks.- Glossary.- Index

Dr. Bernhard Reus is a Senior Lecturer in the Department of Informatics at the University of Sussex, with 15 years experience in teaching computability and complexity.

"This is a textbook about computability and complexity delivered as a one-semester final year module for undergraduates. ... There are quite a few exercises and dozens of important references at the end of each chapter, as well as a lot of interesting historical footnotes throughout. ... book may serve not only as an undergraduate text, but also as a reference source." (Haim Kilov, zbMATH 1376.68003, 2018)

"I think this is a very good update of Neil Jones's brilliant approach at teaching computability and complexity in a nontraditional manner that may resonate with students who are not necessarily deeply interested in mathematical abstractions. ... I think Reus's book deserves a large readership and should be tried out as an alternative text ... in computing and communications courses worldwide." (Sitabhra Sinha, Computing Reviews, January, 2017)"The book under review is a textbook intended to provide the material for an introductory course on the classic theory of algorithms and modern complexity theory for senior undergraduate computer science students. ... the book is a good, concise introduction to the fields of computability and complexity for students, and a good reference for working professionals in all areas of computer science and mathematics." (M. I. Dekhtyar, Mathematical Reviews, November, 2016)