The Halting Problem is one of the most important unsolvable/undecidable problems in the Theory of Computation.
It was introduced and proved undecidable by Alan Turing.
1. Definition
The Halting Problem asks:
Given a Turing Machine \(M\) and an input string \(w\), can we determine whether \(M\) will eventually halt on \(w\) or continue running forever?
In simple words:
Can a computer always predict whether another program will stop or run forever?
The answer is:\[ \boxed{\text{No}} \]
There is no general algorithm that can correctly determine this for every possible program and input.
Therefore, the Halting Problem is undecidable.
2. Example
Suppose we have a program:
START
↓
Take input
↓
Perform calculations
↓
Stop?
/ \
Yes No
↓ ↓
HALT Continue forever
We want another program called HALT to predict what will happen.
It would receive:
HALT(Program, Input)
and return:
YES → Program will halt
NO → Program will run forever
Such a program cannot exist for all possible programs and inputs.
3. Formal Definition
The Halting Problem can be represented by the language:\[ HALT=\{\langle M,w\rangle \mid M \text{ halts on input } w\} \]
where:
- \(M\) = Turing Machine
- \(w\) = input string
- \(\langle M,w\rangle\) = encoded representation of the machine and input.
The question is whether:\[ \langle M,w\rangle \in HALT \]
can always be decided by a Turing Machine.
The answer is No.
Therefore:\[ \boxed{HALT\text{ is undecidable}} \]
4. Proof of Halting Problem
The standard proof uses contradiction.
Step 1: Assume a Halting Machine exists
Suppose there is a machine \(H\) that can determine whether any machine \(M\) halts on input \(w\).
H(M,w)
It gives:
YES → M halts on w
NO → M does not halt on w
Step 2: Construct another machine D
Create a machine \(D\) that takes a machine \(M\) as input.
It uses \(H\) to determine whether \(M\) halts on itself:
D(M):
Run H(M,M)
If H says "HALT"
↓
LOOP FOREVER
If H says "DOES NOT HALT"
↓
HALT
So D does exactly the opposite of what \(H\) predicts.
5. Give D Its Own Description
Now run:\[ D(D) \]
That means machine \(D\) is given itself as input.
There are two possibilities.
Case 1: H says D halts
Then according to the definition of \(D\):
If \(H\) says halt, D loops forever.
So:
H says: D HALTS
D does: DOES NOT HALT
Contradiction.
Case 2: H says D does not halt
According to the definition of \(D\):
If \(H\) says does not halt, D halts.
So:
H says: D DOES NOT HALT
D does: HALTS
Again, contradiction.
6. Conclusion
Both possibilities lead to a contradiction.
Therefore, our original assumption that \(H\) exists must be false.
Hence:\[ \boxed{\text{No algorithm can solve the Halting Problem for all inputs.}} \]
Therefore:\[ \boxed{\text{Halting Problem is Undecidable}} \]
7. Simple Diagram of the Proof
Assume H exists
↓
H predicts whether M halts
↓
Construct D
↓
D does the opposite of H
↓
D(D)
/ \
/ \
H says HALT H says NO HALT
↓ ↓
D loops D halts
↓ ↓
CONTRADICTION CONTRADICTION
\ /
\ /
\ /
↓
H cannot exist
↓
HALTING PROBLEM IS
UNDECIDABLE
8. Why Is the Halting Problem Important?
The Halting Problem establishes a fundamental limitation of computers.
It proves that:
There are some well-defined problems that no computer program can solve for every possible input.
This is important in:
- Theory of Computation
- Compiler design
- Programming languages
- Software verification
- Artificial intelligence
- Algorithm design
9. Halting Problem and Recursive Languages
The language:\[ HALT=\{\langle M,w\rangle\mid M\text{ halts on }w\} \]
is Recursively Enumerable (RE) but not Recursive.
Why?
If \(M\) halts on \(w\), we can simulate \(M\):
M(w)
↓
Eventually halts
↓
Accept
But if \(M\) never halts, our simulation may continue forever.
Therefore:
| Property | HALT |
|---|---|
| Recursively Enumerable | Yes |
| Recursive/Decidable | No |
| Undecidable | Yes |
This is an important exam point.
10. Halting Problem vs Unsolvable Problem
The Halting Problem is a specific example of an unsolvable problem.
Unsolvable Problems
↓
Halting Problem
↓
Undecidable
It demonstrates that not every computational problem has an algorithmic solution.
11. Real-Life Understanding
Consider a program:
while (true)
{
print("Hello");
}
Clearly, this program never stops.
But now consider a very complicated program containing millions of instructions, loops, recursion, and conditions.
The question is:
Can we create one universal program that examines any program + any input and always tells us whether it will eventually stop?
No.
That is exactly what the Halting Problem proves.
12. Important Difference: Halting vs Slow
Do not confuse:
Slow problem with Halting Problem.
Slow:
An algorithm may take:\[ 10^{100} \]
steps, but eventually finishes.
It is still computable.
Halting Problem:
There is no general algorithm that can always determine whether an arbitrary program will eventually finish.
So:
Slow ≠ Unsolvable
5–10 Marks Exam Answer
Halting Problem
The Halting Problem is the problem of determining whether a given Turing Machine \(M\) will halt or continue running indefinitely on a given input \(w\).
It can be represented as:\[ HALT=\{\langle M,w\rangle\mid M\text{ halts on }w\} \]
Alan Turing proved that there is no Turing Machine or algorithm that can correctly decide the Halting Problem for every possible machine and input. Hence, the Halting Problem is undecidable.
The proof is based on contradiction. Assume that a machine \(H\) exists which determines whether any machine halts. Construct another machine \(D\) that does the opposite of \(H\)’s prediction when given a machine as input. When \(D\) is given its own description, i.e. \(D(D)\), both possible predictions of \(H\) lead to a contradiction. Therefore, \(H\) cannot exist.
Thus:\[ \boxed{\text{Halting Problem is Undecidable}} \]
The Halting Problem language is recursively enumerable but not recursive.
Fast Memory Trick
“Assume Predictor → Make Opposite Machine → Give Machine to Itself → Contradiction → Undecidable.”
Or simply:
HALT asks “Will it stop?” — No universal algorithm can always answer.
