Skip to content

11.4 Halting Problem

The undecidable problem of determining whether a Turing machine halts on a given input.

halting problem undecidability computability logic theory

The halting problem asks whether a Turing machine eventually stops.

Given a machine MM and an input word ww, we ask:

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

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

qaccept q_{\mathrm{accept}}

or:

qreject q_{\mathrm{reject}}

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

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:

⟨M,w⟩ \langle M,w\rangle

where MM is a Turing machine and ww is an input word.

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

Recognizable but Not Decidable

The halting problem is recognizable.

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

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

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

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

M will never halt 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:

HALTTM \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:

CaseCorrect answer
MM halts on wwaccept
MM does not halt on wwreject

The theorem says that such a decider does not exist.

Proof Idea

Assume, for contradiction, that there is a decider:

H H

for the halting problem.

Then HH takes input:

⟨M,w⟩ \langle M,w\rangle

and always halts.

It answers:

H(⟨M,w⟩)={accept,if M halts on w, reject,if M does not halt on w. 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 DD that uses HH as a subroutine.

On input ⟨M⟩\langle M\rangle, the machine DD does this:

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

So DD behaves opposite to what HH predicts about self-application.

In symbols:

D(⟨M⟩)={loop forever,if H(⟨M,⟨M⟩⟩)=accept, halt,if H(⟨M,⟨M⟩⟩)=reject. 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 DD runs on its own code:

D(⟨D⟩) D(\langle D\rangle)

There are two cases.

First, suppose DD halts on ⟨D⟩\langle D\rangle.

Then HH must say that DD halts on ⟨D⟩\langle D\rangle.

But by the definition of DD, if HH says this, then DD loops forever.

Contradiction.

Second, suppose DD does not halt on ⟨D⟩\langle D\rangle.

Then HH must say that DD does not halt on ⟨D⟩\langle D\rangle.

But by the definition of DD, if HH says this, then DD halts.

Contradiction again.

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

What the Proof Uses

The proof depends on two earlier ideas.

First, machines can be encoded as strings:

⟨M⟩ \langle M\rangle

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

M(⟨M⟩) M(\langle M\rangle)

This makes self-reference possible.

The contradiction comes from designing DD to disagree with HH on the special input:

⟨D⟩ \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:

There is no single algorithm that works for all programs and all inputs. \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 MM and input ww, we may prove that MM 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:

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

The halting problem asks:

Does M halt on w? \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.