# 11.4 Halting Problem

## 11.4 Halting Problem

The **halting problem** asks whether a Turing machine eventually stops.

Given a machine $M$ and an input word $w$, we ask:

$$
\text{Does } M \text{ halt on input } w?
$$

Here “halt” means that the computation eventually reaches a stopping state, such as:

$$
q_{\mathrm{accept}}
$$

or:

$$
q_{\mathrm{reject}}
$$

If $M$ reaches one of these states after finitely many steps, then $M$ halts on $w$. If the computation continues forever, then $M$ does not halt on $w$.

### The Halting Language

We can define the halting problem as a language:

$$
\mathrm{HALT}_{\mathrm{TM}}
===========================

{\langle M,w\rangle : M \text{ halts on input } w}
$$

The input is an encoding:

$$
\langle M,w\rangle
$$

where $M$ is a Turing machine and $w$ is an input word.

The question is whether this encoded pair belongs to $\mathrm{HALT}_{\mathrm{TM}}$.

### Recognizable but Not Decidable

The halting problem is **recognizable**.

There is a Turing machine that recognizes $\mathrm{HALT}_{\mathrm{TM}}$:

1. Given $\langle M,w\rangle$, simulate $M$ on $w$.
2. If $M$ halts, accept.
3. If $M$ runs forever, keep simulating forever.

So positive cases can be found. If $M$ really halts, simulation eventually sees it.

But negative cases are the problem. If $M$ keeps running, there may be no finite moment when we can safely say:

$$
M \text{ will never halt}
$$

The main theorem says that no algorithm solves this for all machines and inputs.

### Theorem

There is no Turing machine that decides:

$$
\mathrm{HALT}_{\mathrm{TM}}
$$

Equivalently, no algorithm can always determine whether an arbitrary machine halts on an arbitrary input.

To be a decider, a machine must halt on every input and answer correctly:

| Case                     | Correct answer |
| ------------------------ | -------------- |
| $M$ halts on $w$         | accept         |
| $M$ does not halt on $w$ | reject         |

The theorem says that such a decider does not exist.

### Proof Idea

Assume, for contradiction, that there is a decider:

$$
H
$$

for the halting problem.

Then $H$ takes input:

$$
\langle M,w\rangle
$$

and always halts.

It answers:

$$
H(\langle M,w\rangle)=
\begin{cases}
\mathrm{accept}, & \text{if } M \text{ halts on } w,\
\mathrm{reject}, & \text{if } M \text{ does not halt on } w.
\end{cases}
$$

Now we build a new machine $D$ that uses $H$ as a subroutine.

On input $\langle M\rangle$, the machine $D$ does this:

1. Run $H$ on $\langle M,\langle M\rangle\rangle$.
2. If $H$ says that $M$ halts on its own code, then loop forever.
3. If $H$ says that $M$ does not halt on its own code, then halt.

So $D$ behaves opposite to what $H$ predicts about self-application.

In symbols:

$$
D(\langle M\rangle)=
\begin{cases}
\text{loop forever}, & \text{if } H(\langle M,\langle M\rangle\rangle)=\mathrm{accept},\
\text{halt}, & \text{if } H(\langle M,\langle M\rangle\rangle)=\mathrm{reject}.
\end{cases}
$$

Now ask what happens when $D$ runs on its own code:

$$
D(\langle D\rangle)
$$

There are two cases.

First, suppose $D$ halts on $\langle D\rangle$.

Then $H$ must say that $D$ halts on $\langle D\rangle$.

But by the definition of $D$, if $H$ says this, then $D$ loops forever.

Contradiction.

Second, suppose $D$ does not halt on $\langle D\rangle$.

Then $H$ must say that $D$ does not halt on $\langle D\rangle$.

But by the definition of $D$, if $H$ says this, then $D$ halts.

Contradiction again.

Both possibilities lead to contradiction. Therefore the assumed decider $H$ cannot exist.

### What the Proof Uses

The proof depends on two earlier ideas.

First, machines can be encoded as strings:

$$
\langle M\rangle
$$

Second, a machine can be run on the encoding of another machine, even on its own encoding:

$$
M(\langle M\rangle)
$$

This makes self-reference possible.

The contradiction comes from designing $D$ to disagree with $H$ on the special input:

$$
\langle D\rangle
$$

This is a diagonal argument. It is similar in spirit to Cantor’s diagonal proof, but applied to computation.

### Meaning of the Result

The halting problem does not say that we can never prove a particular program halts.

Many specific programs can be analyzed. For example, a program with a simple loop over a finite list clearly halts.

The theorem says something stronger and more precise:

$$
\text{There is no single algorithm that works for all programs and all inputs.}
$$

So the failure is global, not local.

For some individual machine $M$ and input $w$, we may prove that $M$ halts or prove that it does not halt. But no universal decision procedure can always do this automatically.

### Relation to Program Analysis

The halting problem explains why perfect program analysis is impossible.

A tool may detect many infinite loops, but it cannot detect all of them while always giving correct answers.

A compiler may prove that many programs terminate, but it cannot prove termination for every terminating program and also reject every non-terminating one.

This is not a limitation of current technology. It is a mathematical limit.

### Accepting vs Halting

It is useful to distinguish two related questions.

The acceptance problem asks:

$$
\text{Does } M \text{ accept } w?
$$

The halting problem asks:

$$
\text{Does } M \text{ halt on } w?
$$

A machine may halt by accepting or rejecting. Therefore halting is broader than accepting.

The languages are:

$$
A_{\mathrm{TM}}
===============

{\langle M,w\rangle : M \text{ accepts } w}
$$

and

$$
\mathrm{HALT}_{\mathrm{TM}}
===========================

{\langle M,w\rangle : M \text{ halts on } w}
$$

Both are central undecidable problems.

The halting problem marks a boundary in computation. Some questions can be asked clearly, encoded precisely, and still have no algorithmic solution.