The Halting Problem is determining whether a computer program will eventually stop or run forever. Creating a general algorithm that can accurately predict this for all programs is impossible. Alan Turing's proof showed no way to solve the Halting Problem for all cases.
Halting means that the system will either accept or halt(reject) a certain input to avoid entering an infinite loop. The decision of whether or not a specific Turning machine should halt is known as the Halting Problem of Turning Machines.
The halting problem is one of the most well-known problems proven to be undecidable. In this article, we will learn about the Halting Problem in the Theory of Computation.
What is the Halting Problem?
The halting problem was proposed by Alan Turing in 1936. The halting problem is a fundamental issue in theory and computation. The halting problem is the problem of determining whether a computer program will halt or run forever.
Before moving on to the proof, let's first understand some terms.
1. Turing Machine
A Turing machine is a computational mathematical model. It is a type of CPU that controls all data manipulation performed by a computer. Turing machines can be either halting or non-halting, depending on the algorithm and the input associated with the algorithm.
2. Decision Problems
A decision problem has only two possible outcomes (yes or no) on any input. In computability and computational complexity theories, a decision problem for a given program can be expressed as a yes/no question of the input values.
3. Computability theory
An undecidable problem is a sort of computational problem requiring a yes/no answer but where no computer program can give the proper answer all of the time; that is, any possible algorithm or program would sometimes give the wrong answer or run forever without providing any answer.
(See Decidability and Undecidability)
Proof by Contradiction
Step 1: Assume we can create a machine called HM(P, I), where HM is the Halting machine, P is the program, and I is the input. After receiving both inputs, the machine HM will output whether or not the program P terminates.
Step 2: Now, create an inverted halting machine IM that takes a program P as input and,
- Loops forever If HM returns YES.
- Halts if HM returns NO.
Step 3: Now, take a situation where the program IM is passed to the IM function as an input. Here, we got a contradiction. Let's understand how.
It is impossible for the outer function to halt if its inner function is in a loop(RHS), and it is likewise impossible for the outer function to halt even if its inner function is halting(LHS). So both conditions are non-halting for the IM machine, despite our above assumptions.
Hence, the halting problem is undecidable.
Also read, Arden's theorem