The Halting Problem and Computability

One of the most profound results in Computer Science is that there are problems which no computer can ever solve, regardless of how much time or memory is available. The most famous example is the Halting Problem, proved undecidable by Alan Turing in 1936.

---

Decidable vs Undecidable Problems

Classification	Definition	Example
Decidable	A problem for which an algorithm exists that always terminates with the correct Yes/No answer	"Is this number prime?"
Undecidable	No algorithm exists that can always terminate with the correct answer for all possible inputs	The Halting Problem

A decidable problem has an algorithm that:

1. Always halts (terminates)
2. Always gives the correct answer

An undecidable problem has no such algorithm — for any proposed algorithm, there will always be some inputs for which it gives the wrong answer or never terminates.

---

The Halting Problem

Statement

Given a description of a program P and an input I, determine whether P will eventually halt (terminate) or run forever when executed on input I.

Formally: Does there exist an algorithm H such that:

• H(P, I) = "halts" if P halts on input I
• H(P, I) = "loops" if P runs forever on input I

Turing's Proof (by Contradiction)

Turing proved that no such algorithm H can exist. The proof uses a clever diagonalisation argument:

1. Assume (for contradiction) that H exists — a program that can correctly decide whether any program halts on any input.

2. Construct a new program D that takes a program P as input:

   PROGRAM D(P):
       IF H(P, P) = "halts" THEN
           loop forever
       ELSE
           halt
   

   D does the opposite of what H predicts.

3. Run D on itself: What happens when we call D(D)?

   • Case 1: H says D(D) halts. Then D enters the infinite loop (by its definition). So D(D) does NOT halt. Contradiction!
   • Case 2: H says D(D) loops. Then D halts (by its definition). So D(D) DOES halt. Contradiction!

4. Both cases lead to a contradiction. Therefore, our assumption was wrong — H cannot exist.

---

Why the Halting Problem Matters

Implication	Explanation
Limits of computation	Not all problems are solvable by algorithms
No perfect debugging tool	You cannot write a program that always correctly determines whether another program will crash or loop
No perfect virus scanner	You cannot determine in general whether a piece of code will exhibit malicious behaviour
Software verification	Perfect automatic verification of all programs is impossible
Foundation of complexity theory	Understanding what cannot be computed helps us understand what can

---

Other Undecidable Problems

The Halting Problem is not the only undecidable problem. Many others have been proved undecidable by reduction — showing that if we could solve the new problem, we could use it to solve the Halting Problem, which we know is impossible.