# John Lindsay Orr

$\newcommand{\CC}{\mathbb{C}} \newcommand{\NN}{\mathbb{N}} \newcommand{\RR}{\mathbb{R}} \newcommand{\H}{\mathcal{H}} \newcommand{\e}{\epsilon} \newcommand{\x}{\mathbf{x}} \newcommand{\y}{\mathbf{y}}$

# The Halting Problem

There is an algorithm to associate every Turing machine with a natural number, called the Turing number of that machine. Thus we can consider the set $S$ of all pairs $(m,n)$ in $\NN\times\NN$ where $m$ is a Turing number and the corresponding Turing machine will halt given input $n$.

For any Turing machine $T$ and input $n\in\NN$ write $T(n)$ for the output of $T$ with input $n$. This output is either a natural number, if $T$ halts, or undefined if $T$ does not halt. The set $\NN\times\NN$ can be encoded as natural numbers to be input to $T$, for example by encoding $m$ and $n$ as unary numbers as strings of $1$'s, with a single $0$ separating them, so we also write $T(m,n)$, where this encoding is implied.

If the Halting problem is algorithmically decidable then there is a Turing machine $H$ which outputs $1$ if its input is a pair $(m,n)$ from $S$ and $0$ otherwise. From $H$ we can clearly build a Turing machine $G$ which halts with output $0$ if $H(k, k) = 0$ and runs without halting if $H(k, k) = 1$. Let $g$ be the Turing number of $G$ and consider $H(g, g)$. On one hand, if $H(g, g) = 0$ then $G(g)$ halts, and so $H(g, g) = 1$, a contradiction. On the other hand, if $H(g, g) = 1$ then $G(g)$ does not halt, and so $H(g, g) = 0$, also a contradiction. Thus we conclude that the Halting problem is not algorithmically decidable.