The halting problem is the first major example of an undecidable problem. Once we know that one problem is undecidable, we can use it to prove that many other problems are undecidable too.

A decision problem asks for a yes-or-no answer. In computability theory, we usually represent a decision problem as a language:

A machine decides $L$ if it always halts and gives the correct answer:

If such a machine exists, then $L$ is decidable.

If no such machine exists, then $L$ is undecidable.

Recognizable and Decidable

A language is recognizable if there is a machine that accepts exactly the strings in the language.

For $w \in L$, the machine eventually accepts.

For $w \notin L$, the machine may reject or run forever.

So recognizable means we can eventually confirm yes-instances, but we may fail to confirm no-instances.

A language is decidable if both yes and no cases are handled in finite time.

Every decidable language is recognizable, but not every recognizable language is decidable.

The halting language:

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

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

is recognizable but undecidable.

Reductions

A reduction transforms one problem into another.

Suppose we have two languages:

and

A many-one reduction from $A$ to $B$ is a computable function:

such that:

We write:

This means that problem $A$ can be translated into problem $B$.

The direction matters. If:

and $B$ is decidable, then $A$ is decidable.

So if $A$ is known to be undecidable and:

then $B$ must also be undecidable.

Otherwise, a decider for $B$ would give a decider for $A$.

Proving Undecidability by Reduction

To prove that a problem $B$ is undecidable, we usually do this:

1. Start with a known undecidable problem $A$.
2. Build a computable transformation $f$.
3. Show: $$w \in A \quad \Longleftrightarrow \quad f(w) \in B$$
4. Conclude that $B$ is undecidable.

This is a standard pattern. It lets us reuse one hard impossibility result many times.

Example: Emptiness of Turing Machine Languages

Define:

$$ E_{\mathrm{TM}}

{\langle M\rangle : L(M)=\varnothing} $$

This problem asks whether a machine accepts no strings at all.

We will show that $E_{\mathrm{TM}}$ is undecidable.

The idea is to reduce from the acceptance problem:

$$ A_{\mathrm{TM}}

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

Given an input:

construct a new machine $N$ as follows.

On input $x$:

1. Ignore $x$.
2. Simulate $M$ on $w$.
3. If $M$ accepts $w$, accept $x$.

Now observe:

If $M$ accepts $w$, then $N$ accepts every input $x$. So:

In particular:

If $M$ does not accept $w$, then $N$ accepts no input. So:

Therefore:

This gives a reduction from $A_{\mathrm{TM}}$ to the complement of $E_{\mathrm{TM}}$. It shows that deciding emptiness would let us decide acceptance, which is impossible.

So $E_{\mathrm{TM}}$ is undecidable.

Example: Equivalence of Machines

Define:

$$ EQ_{\mathrm{TM}}

{\langle M_1,M_2\rangle : L(M_1)=L(M_2)} $$

This problem asks whether two Turing machines accept exactly the same language.

It is undecidable.

One way to see this is to reduce emptiness to equivalence.

Let $M_{\varnothing}$ be a fixed machine that rejects every input. Then:

Given a machine $M$, ask whether:

This is exactly the question whether:

So if $EQ_{\mathrm{TM}}$ were decidable, then $E_{\mathrm{TM}}$ would be decidable.

But $E_{\mathrm{TM}}$ is undecidable. Therefore:

is undecidable.

Rice’s Theorem

Many undecidability results about Turing machines are instances of one general theorem.

Rice’s theorem says that every nontrivial semantic property of Turing-machine languages is undecidable.

A property is semantic if it depends only on the language accepted by the machine, not on the machine’s internal code.

A property is nontrivial if some machines have it and some machines do not.

Examples of semantic properties:

Each of these properties is undecidable by Rice’s theorem, provided we ask the question for arbitrary Turing machines.

Rice’s theorem does not apply to purely syntactic properties. For example:

This is decidable by inspecting the machine description.

The theorem concerns what the machine computes, not how the machine is written.

Totality

Another important undecidable problem is totality.

Define:

$$ \mathrm{TOTAL}_{\mathrm{TM}}

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

This asks whether a machine is total as a function or decision procedure.

It is undecidable.

The intuition is simple. If we could decide whether $M$ halts on every input, then we could solve many termination questions. But arbitrary termination behavior is already undecidable.

Totality is even harder than the ordinary halting problem in some formal classifications, but the key point here is that no algorithm can decide it for all machines.

Decidable Islands

Undecidability does not mean every problem is hopeless.

Many restricted problems are decidable. For example:

• emptiness for finite automata is decidable
• equivalence for deterministic finite automata is decidable
• membership for context-free grammars is decidable
• type checking for many programming languages is decidable
• termination for simple loop-free programs is decidable

The boundary matters. Turing machines are powerful enough to express arbitrary computation. Once a model reaches that level of power, many global questions about its behavior become undecidable.

Why Reductions Matter

Reductions organize undecidable problems.

They let us say that one problem is at least as hard as another:

If $A$ is impossible to decide, and $A$ reduces to $B$, then $B$ is also impossible to decide.

This gives computability theory a structure. Problems are not merely labeled decidable or undecidable. They are compared by how much computational difficulty they contain.

Undecidability results show that there are precise limits to algorithmic reasoning. The issue is not lack of cleverness or lack of hardware. Some decision problems cannot be solved by any algorithm.