The Halting Problem asks whether there exists an algorithm that can determine, for any arbitrary program and input, whether the program will eventually halt (terminate) or run forever.
Formally, we define HALTTM = {(M, w) | The Turing machine M halts on input w}. The question is: Is HALTTM decidable?
Alan Turing proved in 1936 that the halting problem is undecidable, meaning no algorithm can solve it for all possible inputs.
The Halting Problem was one of the first problems proven to be algorithmically unsolvable. It established fundamental limits on what computers can do.
Turing's work on the Halting Problem predated actual computers and helped establish the theoretical foundations of computer science.
The undecidability of the Halting Problem means we cannot create a perfect debugger that can always determine if a program will get stuck in an infinite loop.
Halting Problem
Undecidable
Imagine you're asked to create a program H that can analyze any other program P and determine whether P will halt or run forever when given some input.
What happens if we create a new program D that does the following:
Now, what happens if we run D with itself as input? If D halts, then by its definition, it should run forever. If D runs forever, then by its definition, it should halt. This contradiction proves that our halting detector H cannot exist!