Skip to content
Home » Halting Problem

Halting Problem

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:

PropertyHALT
Recursively EnumerableYes
Recursive/DecidableNo
UndecidableYes

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.