Solution
A problem is unsolvable if no algorithm can be created that will provide a solution in all cases. These problems do not have a general procedure that can guarantee a solution for every possible input.
The Halting Problem asks whether a given program will eventually halt (finish running) or continue to run forever, for a given input.
Alan Turing proved that no general algorithm can solve the Halting Problem for all possible program-input pairs. If such an algorithm existed, it would have to decide, for every program and every input, whether that program stops. Turing showed that this leads to a contradiction: one can construct a program that behaves in a way that the supposed algorithm cannot classify correctly. Therefore no algorithm can solve the problem in all cases.
Implications in computer science:
- It is a fundamental example of an unsolvable problem. Not every well-stated question about programs can be answered by a computer.
- It shows that solvability must be considered before investing time in an algorithm. Working on a problem that cannot be resolved by any algorithm wastes time and resources.
- It limits what we can automatically prove about software: there is no universal method that can always tell whether an arbitrary program will finish, loop forever, or satisfy every property of that kind.
- It sits at the foundation of computability theory and helps separate solvable problems (such as computing the GCD with the Euclidean algorithm) from unsolvable ones.