This is a book about the ‘Halting Problem’, arguably the most (in)famous computer-related problem: can an algorithm decide in finite time whether an arbitrary computer program eventually stops? This seems a dull, petty question: after all, you run the program and wait till it stops. However, what if the program does not stop in a reasonable time, a week, a year, or a decade? Can you infer that it will never stop? The answer is negative. Does this raise your interest? If not, consider these questions: Can mathematics be done by computers only? Can software testing be fully automated? Can you write an anti-virus program which never needs any updates? Can we make the Internet perfectly secure? Your guess is correct: the answer to each question is negative. The Halting Problem is ‘hidden’ in many subjects, from logic (is mathematics free of contradictions?), physics (is quantum randomness perfect?), to philosophy (do humans have free will, or do our brains generate our thoughts and decisions in a deterministic way?) and quantum computing (why we don’t have a quantum Halting Problem?) — this book will visit each of them.

Written in an informal and thought-provoking language, supported with suggestive illustrations and applications and almost free of arcane mathematics (formal arguments are relegated to particular parts dedicated to the mathematically-oriented reader), the book will stimulate the curiosity and participation of the reader interested in the consequences of the limits of computing and in various attempts to cope with them.

Contents:

• From Entscheidungsproblem to the Halting Problem


• Incompleteness and Halting


• Famous Mathematical Statements and the Halting Problem


• Sagacious Applications of the Halting Theorem


• The Halting Problem and Beyond


• A Formal Approach to Incompleteness and Halting


• Historical and Philosophical Notes

Readership: Undergraduate and graduate students, researchers and practitioners in the fields of computer science, mathematics, logic, philosophy, physics, and a large category of educated readers.

‘Journey with Calude through this varied terrain of spectacular insights. In an age when super AI’s menace, it is good to see what the unfettered human spirit can accomplish, and be proud.’ – Gregory Chaitin Author of Algorithmic Information Theory

‘Every page of this delightful book has another gem that contains either an insight into the halting problem or a connection between the halting problem and a different area. Cristian Calude, a world-class researcher, has done a magnificent job collecting these ideas and making them accessible to everyone.’ – Noson S Yanofsky Author of The Outer Limits of Reason: What Science, Mathematics and Logic Cannot Tell Us

Key Features:

• People falsely believe that there are no limits to what computers can do. The centre-stage is taken by a single result which has many consequences, from science and arts to daily life


• There is no other book treating this topic


• The book is written in an informal and thought-provoking language


• The book will interest a large audience, from experts in computing and mathematics to educated laymen