---
title: "Halting problem is undecidable"
subject: "Theory of Computation"
chapter: 5
key: "semester_3/theory_of_computation:halting-problem-undecidable"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/halting-problem-undecidable
site: BCT Engineering
---

# Halting problem is undecidable

Theory of Computation · Chapter 5: Undecidability

- Asked in: 2072 Chaitra; 2072 Kartik (asked 2 times)
- Video: [Undecidability of the Halting Problem](https://www.youtube.com/watch?v=_eM0-KfAmhQ) — Neso Academy
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/halting-problem-undecidable
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-5

## Question

Explain the halting problem and show that the halting problem is undecidable.

## Short answer

The halting problem asks whether a given TM M halts on input w. Assume a decider H exists; build D that runs H on ⟨M,⟨M⟩⟩: if H accepts, D loops; if H rejects, D halts. Then D on ⟨D⟩ leads to contradiction, so no such H exists. Hence the halting problem is undecidable.

## Answer

#### The halting problem
**Given** a Turing machine M and an input w, **decide** whether M halts (stops) when started on w.
As a language: HALT = { ⟨M, w⟩ : M halts on input w }. The question is whether HALT is **decidable**, that is, whether some TM always halts and answers correctly.

HALT is **recursively enumerable**: simulate M on w and accept if the simulation halts. But, as shown below, it is **not recursive**.

#### Theorem: HALT is undecidable
**Proof (by contradiction, diagonalisation).** Suppose a TM H decides HALT: H(⟨M, w⟩) halts and accepts if M halts on w, and halts and rejects if M loops on w.

Build a new TM D that takes the description ⟨M⟩ of a machine as input:
1. Run H on ⟨M, ⟨M⟩⟩ (ask: does M halt when given its own description?).
2. If H **accepts** (M halts on ⟨M⟩), then D **loops forever**.
3. If H **rejects** (M loops on ⟨M⟩), then D **halts**.

```text
 <M> ─► [ H ] ── accept ─► loop forever
              └─ reject ─► halt
              (this whole box is machine D)
```

Now run D on its own description ⟨D⟩:
- Suppose D halts on ⟨D⟩. Then H accepted ⟨D, ⟨D⟩⟩, and by step 2 D loops forever. Contradiction.
- Suppose D loops on ⟨D⟩. Then H rejected ⟨D, ⟨D⟩⟩, and by step 3 D halts. Contradiction.

Either way we get a contradiction, so the machine H cannot exist. **The halting problem is undecidable.**

#### Consequences
- No program can check, for every program and input, whether it terminates.
- Many other problems are undecidable by reduction from HALT (for example, whether a TM accepts the empty string, whether a TM's language is empty, program equivalence).
- The complement of HALT is not even RE.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does the halting problem ask?
   A. Whether M halts on input w
   B. Whether M accepts w
   C. Whether L is regular
   D. Whether M has a halting state
   Answer: A. Given M and w, decide whether M halts. (Key point: Statement)

2. Which technique proves HALT undecidable?
   A. Pumping lemma
   B. Contradiction by diagonalisation
   C. Induction on length
   D. Closure properties
   Answer: B. Assume a decider H and build D that does the opposite of H on <M,<M>>. (Key point: Proof method)

3. What does D do if H accepts <M,<M>>?
   A. Halts
   B. Loops forever
   C. Accepts
   D. Rejects
   Answer: B. D loops if H says M halts, and halts if H says M loops. (Key point: Machine D)

4. Why does running D on <D> give a contradiction?
   A. D halts exactly when D loops
   B. D has no description
   C. H is too slow
   D. D is infinite
   Answer: A. Either outcome contradicts what H predicted, so H cannot exist. (Key point: Contradiction)