---
tag: Z7TN2B35B0
kind: statement
role: theorem
name: Undecidability of the halting problem
msc: [03D10, 03D25]
uses: [758EYCN27B, PPGD5KW8JC, MFJXPAF0R0]
about: [758EYCN27B, PPGD5KW8JC]
sources:
  - url: https://en.wikipedia.org/wiki/Halting_problem
---

## Statement

Fix a [[Gödel numbering|MFJXPAF0R0]] $e \mapsto M_e$ of all [[Turing machines|758EYCN27B]] with input and output in the natural numbers.
Let $H = \set{(e, x) \in \N^2 : M_e \text{ halts on input } x}$.
Then $H$ is not a [[computable set|PPGD5KW8JC]]: no Turing machine halts on every input $(e, x)$ and outputs $1$ if $(e, x) \in H$ and $0$ otherwise.

## Remarks

Suppose a machine $D$ decides $H$.
Build a machine $N$ that, on input $e$, runs $D$ on $(e, e)$, loops forever if the answer is $1$, and halts if the answer is $0$.
Let $n$ be a number of $N$.
Then $N$ halts on $n$ if and only if $(n, n) \notin H$, that is, if and only if $N$ does not halt on $n$, a contradiction.

The set $H$ is computably enumerable, since a universal machine halts on $(e, x)$ exactly when $M_e$ halts on $x$.
So $H$ is an example of a computably enumerable set that is not computable.
By the same argument, the diagonal set $K = \set{e : M_e \text{ halts on input } e}$ is not computable.

## Explanations

### L1 human

There is no general method to tell, for an arbitrary program and input, whether the program will eventually stop.
One can run the program and wait, but if it has not stopped yet one never knows whether it will.
The proof imagines a perfect halting tester and builds a program that does the opposite of what the tester predicts about itself.

### L2 human

This result goes back to Turing's paper of 1936, and it is the standard first example of an undecidable problem.
Most other undecidability results are proved by reducing the halting problem to them.
Examples are [[Rice's theorem|AKDR5YBBE2]], the undecidability of first-order validity, and the negative solution of [[Hilbert's tenth problem|X8TVJSVTD4]].
In the [[arithmetical hierarchy|7CVJCQKY41]], $H$ is $\Sigma^0_1$-complete.