Reducibility and More Undecidable Problems

Transferring impossibility through computable transformations

From one impossible problem to many

We know that \(A_{TM}\) is undecidable and that \(\overline{A_{TM}}\) is not even Turing-recognizable.

To prove that additional problems are undecidable, we use reducibility:

Transform instances of a known hard problem into instances of a new problem so that solving the new problem would solve the known one.

Reduction is the main technique for establishing the undecidability of additional problems.

Under the Church–Turing thesis, these results concern all algorithms, not merely programs written in Turing-machine notation.

The Halting Problem

Definition

The halting problem is

\[ HALT_{TM} = \{\langle M,w\rangle:M\text{ halts on }w\}. \]

Halting includes accepting or rejecting. The no-instances are computations that run forever.

Turing introduced this problem in his foundational work on computable numbers. It is closely related to

\[ A_{TM} = \{\langle M,w\rangle:M\text{ accepts }w\}. \]

An oracle-style reduction

Assume, for contradiction, that a decider \(R\) exists for \(HALT_{TM}\). We could decide \(A_{TM}\) as follows.

On input \(\langle M,w\rangle\):

1. Run \(R\) on \(\langle M,w\rangle\).
2. If \(R\) says that \(M\) does not halt, reject.
3. If \(R\) says that \(M\) halts, simulate \(M\) on \(w\).
4. Because \(R\) guaranteed termination, wait for \(M\) to halt.
5. Accept if \(M\) accepts; reject if \(M\) rejects.

This would decide \(A_{TM}\), contradicting its undecidability. Therefore,

\[ HALT_{TM}\text{ is undecidable}. \]

A hypothetical halting decider would make the TM acceptance problem decidable.

A mapping reduction from (A_{TM})

Given \(\langle M,w\rangle\), construct a new TM \(M'\) that behaves on any input \(x\) as follows:

M'(x):
    Simulate M on w.
    If M accepts w, accept x.
    If M rejects w, loop forever.

If \(M\) loops on \(w\), then \(M'\) also loops. Thus \(M'\) halts on a fixed input such as \(\varepsilon\) exactly when \(M\) accepts \(w\):

\[ \langle M,w\rangle\in A_{TM} \iff \langle M',\varepsilon\rangle\in HALT_{TM}. \]

The function

\[ f(\langle M,w\rangle)=\langle M',\varepsilon\rangle \]

is computable: a TM can mechanically write the description of \(M'\) from the descriptions of \(M\) and \(w\).

Therefore,

\[ A_{TM}\le_m HALT_{TM}. \]

If \(HALT_{TM}\) were decidable, composing \(f\) with its decider would decide \(A_{TM}\). Hence \(HALT_{TM}\) is undecidable.

Why the halting problem matters

A halting decider would resolve questions far beyond debugging.

Suppose a program systematically searches for a counterexample to a mathematical conjecture and halts only when it finds one. A halting decider could tell us whether such a counterexample exists.

For Fermat’s Last Theorem, one could imagine a program enumerating positive integers \(x,y,z,n\) with \(n>2\) and halting if

\[ x^n+y^n=z^n. \]

The theorem says this search never halts. More generally, termination behavior can encode open mathematical questions such as the existence of an odd perfect number.

A general solution to halting would answer whether arbitrary searches ever find a result.

Undecidability does not make termination analysis useless. Static analyzers can solve restricted cases, prove termination for many programs, or conservatively report “unknown.” What is impossible is a correct algorithm that settles every program-input pair.

Understanding Reductions

Direction matters

Write

\[ A\le_m B \]

when \(A\) is mapping reducible to \(B\). This means a computable function transforms each instance \(x\) of \(A\) into an instance \(f(x)\) of \(B\) such that

\[ x\in A \iff f(x)\in B. \]

The interpretation is:

• if we could solve \(B\), we could solve \(A\);
• \(B\) is at least as hard as \(A\); and
• \(A\) is no harder than \(B\).

A reduction converts an instance of problem \(A\) into an equivalent instance of problem \(B\).

To prove that \(B\) is hard, reduce from a known hard problem to \(B\):

\[ \text{known hard problem}\le_m\text{new problem}. \]

Reversing the direction does not establish the desired conclusion.

The key equivalence

Every mapping reduction must justify

\[ x\in A\iff f(x)\in B. \]

Prove both directions:

1. if \(x\) is a yes-instance of \(A\), then \(f(x)\) is a yes-instance of \(B\);
2. if \(x\) is a no-instance of \(A\), then \(f(x)\) is a no-instance of \(B\).

The conversion must also be total and computable: it must halt and produce a valid output for every encoded input.

If the equivalence fails in even one case—often when the simulated machine rejects versus loops—the reduction does not work.

Composition with a decider

If \(f\) reduces \(A\) to \(B\) and \(D_B\) decides \(B\), then a decider for \(A\) is:

D_A(x):
    Compute f(x).
    Run D_B on f(x).
    Return D_B's answer.

Because both computations halt,

\[ A\le_m B\text{ and }B\text{ decidable} \Longrightarrow A\text{ decidable}. \]

Taking the contrapositive gives:

\[ A\le_m B\text{ and }A\text{ undecidable} \Longrightarrow B\text{ undecidable}. \]

More Undecidable Problems

Does a TM accept the empty string?

Define

\[ ACCEPTS_\varepsilon = \{\langle M\rangle:M\text{ accepts }\varepsilon\}. \]

Reduce \(A_{TM}\) to \(ACCEPTS_\varepsilon\). Given \(\langle M,w\rangle\), construct \(M'\):

M'(x):
    Ignore x.
    Write w on the tape.
    Simulate M on w.
    Accept exactly if M accepts.

Then

\[ \langle M,w\rangle\in A_{TM} \iff \langle M'\rangle\in ACCEPTS_\varepsilon. \]

A decider for \(ACCEPTS_\varepsilon\) would decide \(A_{TM}\). Hence \(ACCEPTS_\varepsilon\) is undecidable.

TM language emptiness

Define

\[ E_{TM} = \{\langle M\rangle:L(M)=\varnothing\}. \]

Given \(\langle M,w\rangle\), construct \(M_1\):

M1(x):
    If x differs from w, reject.
    Simulate M on w.
    Accept if M accepts.

Then

\[ L(M_1)= \begin{cases} \{w\},&M\text{ accepts }w,\\ \varnothing,&M\text{ does not accept }w. \end{cases} \]

Therefore,

\[ \langle M,w\rangle\in A_{TM} \iff \langle M_1\rangle\notin E_{TM}. \]

If \(E_{TM}\) had a decider, we could run it and reverse its answer to decide \(A_{TM}\). Thus \(E_{TM}\) is undecidable. The reversal is legitimate because a decider always halts.

Does a TM accept anything?

Define

\[ NONEMPTY_{TM} = \{\langle M\rangle:L(M)\ne\varnothing\}. \]

This is the complement of \(E_{TM}\) and is therefore undecidable.

Alternatively, reduce \(ACCEPTS_\varepsilon\) directly. Given \(M\), construct \(M'\) that ignores its input and simulates \(M\) on \(\varepsilon\):

\[ L(M')= \begin{cases} \Sigma^*,&M\text{ accepts }\varepsilon,\\ \varnothing,&M\text{ does not accept }\varepsilon. \end{cases} \]

Thus \(M'\) accepts something exactly when \(M\) accepts \(\varepsilon\).

Does a TM accept every string?

Define

\[ ALL_{TM} = \{\langle M\rangle:L(M)=\Sigma^*\}. \]

Use the same construction: \(M'\) ignores its input and simulates \(M\) on \(\varepsilon\). Then

\[ \langle M\rangle\in ACCEPTS_\varepsilon \iff \langle M'\rangle\in ALL_{TM}. \]

Therefore \(ALL_{TM}\) is undecidable.

Does a TM recognize a regular language?

Define

\[ REGULAR_{TM} = \{\langle M\rangle:L(M)\text{ is regular}\}. \]

Assume a decider \(R\) exists. Given \(\langle M,w\rangle\), construct \(M_2\):

M2(x):
    If x has the form 0^n 1^n, accept.
    Otherwise simulate M on w.
    Accept if M accepts w.

Then

\[ L(M_2)= \begin{cases} \Sigma^*,&M\text{ accepts }w,\\ \{0^n1^n:n\ge0\},&M\text{ does not accept }w. \end{cases} \]

The first language is regular; the second is not. Therefore,

\[ \langle M,w\rangle\in A_{TM} \iff \langle M_2\rangle\in REGULAR_{TM}. \]

Running \(R\) on \(\langle M_2\rangle\) would decide \(A_{TM}\), a contradiction. Hence \(REGULAR_{TM}\) is undecidable.

The regularity reduction makes the constructed language either \(\Sigma^*\) or the nonregular language \(\{0^n1^n\}\).

Rice’s Theorem

Statement

A property of Turing-recognizable languages is semantic if it depends only on the language recognized, not on the syntax of the machine description.

Such a property is nontrivial if at least one Turing-recognizable language has it and at least one does not.

Rice’s Theorem. Every nontrivial semantic property of Turing-recognizable languages is undecidable.

Examples include:

• Is the language empty?
• Is the language finite or infinite?
• Is the language regular?
• Does the language contain the string 001?
• Is the language equal to \(\Sigma^*\)?

Rice’s theorem generalizes many reductions concerning properties of the language recognized by a TM.

What Rice’s theorem does not cover

Rice’s theorem concerns the recognized language, not the machine’s implementation.

It does not directly apply to questions such as:

• Does the machine have exactly ten states?
• Does its description contain a transition writing symbol 1?
• Does it ever move its head left?
• Does it halt within 100 steps?

Some behavioral questions are still undecidable, but they require separate arguments.

Proof idea

Let \(P\) be a nontrivial property. First assume

\[ \varnothing\notin P. \]

Because \(P\) is nontrivial, choose a TM \(T_P\) whose language has property \(P\).

Assume a decider \(D_P\) exists for the question “Does \(L(T)\) have property \(P\)?” We use it to decide \(A_{TM}\).

Given \(\langle M,w\rangle\), construct \(N\):

N(x):
    Simulate M on w.
    If M accepts w, simulate T_P on x.
    Accept exactly when T_P accepts x.

Then

\[ L(N)= \begin{cases} L(T_P),&M\text{ accepts }w,\\ \varnothing,&M\text{ does not accept }w. \end{cases} \]

Because \(L(T_P)\) has \(P\) and \(\varnothing\) does not,

\[ \langle M,w\rangle\in A_{TM} \iff \langle N\rangle\in P. \]

The supposed decider \(D_P\) would decide \(A_{TM}\), a contradiction.

If \(\varnothing\in P\), apply the argument to the complementary property “does not have \(P\),” which is also nontrivial. Decidability of \(P\) and its negation are equivalent by reversing a decider’s output.

The machines in the proof

Name	Role
\(M\)	Machine from the \(A_{TM}\) input
\(w\)	Input paired with \(M\)
\(T_P\)	Fixed machine whose language has property \(P\)
\(N\)	Constructed machine whose language depends on whether \(M\) accepts \(w\)
\(D_P\)	Hypothetical decider for property \(P\)
\(D_A\)	Resulting impossible decider for \(A_{TM}\)

The creative heart is the equivalence

\[ M\text{ accepts }w \iff L(N)\text{ has }P. \]

Mapping Reducibility

Formal definition

Language \(A\) is mapping reducible to language \(B\), written

\[ A\le_m B, \]

if there is a total computable function

\[ f:\Sigma^*\rightarrow\Sigma^* \]

such that every \(w\) satisfies

\[ w\in A \iff f(w)\in B. \]

The function \(f\) is called a mapping reduction or many-one reduction.

A computable mapping transforms every instance while preserving yes and no answers.

This is stricter than merely using a solver for \(B\) as an arbitrary subroutine. A mapping reduction makes one computable transformation and asks one membership question about the result.

Fundamental consequences

Decidability transfers downward

If \(A\le_m B\) and \(B\) is decidable, then \(A\) is decidable.

Undecidability transfers upward

Taking the contrapositive:

\[ A\le_m B \quad\text{and}\quad A\text{ undecidable} \Longrightarrow B\text{ undecidable}. \]

Recognizability transfers downward

If \(A\le_m B\) and \(B\) is recognizable, then \(A\) is recognizable.

Nonrecognizability transfers upward

Taking the contrapositive:

\[ A\le_m B \quad\text{and}\quad A\text{ not recognizable} \Longrightarrow B\text{ not recognizable}. \]

This makes \(\overline{A_{TM}}\) a useful source problem for proving that other languages are not recognizable.

A reduction checklist

When writing a reduction proof:

1. Define the source and target languages precisely.
2. State the known status of the source problem.
3. Assume a decider or recognizer for the target when using contradiction.
4. Define the computable transformation on an arbitrary source instance.
5. Explain how the produced machine behaves in every relevant case.
6. Prove the iff statement in both directions.
7. Describe the resulting solver for the source problem.
8. State the contradiction and conclusion.

The proof resides in the computable transformation and its correctness, not in a claim that two problems merely seem equally difficult.

Practice Problems

Determine whether each problem is decidable. If you claim undecidability, identify a suitable source problem and outline the reduction.

1. Given a TM \(T\), does it ever leave its initial state when started on a blank tape?
2. Given a TM \(T\) and a designated nonhalting state \(q\), does \(T\) ever enter \(q\) when started on a blank tape?
3. Given \(\langle T,w\rangle\), does \(T\) loop forever on \(w\)?
4. Given a TM \(T\), is there any input on which \(T\) loops forever?
5. Given \(\langle T,a\rangle\), does \(T\) ever write tape symbol \(a\) on some input?
6. Given two TMs, is one recognized language a subset of the other?

For each, ask first whether it is a semantic property of \(L(T)\), making Rice’s theorem relevant, or a property of the machine’s execution, requiring a direct reduction.

Check your understanding

1. What does \(A\le_m B\) say about the relative difficulty of \(A\) and \(B\)?
2. Which direction should a reduction go when proving \(B\) undecidable?
3. Why must the transformation be computable and always halt?
4. Why is the iff statement more than a formality?
5. How does the reduction to \(HALT_{TM}\) handle rejection differently from acceptance?
6. What distinguishes a semantic property from a syntactic property of a TM?
7. Why does Rice’s theorem require the property to be nontrivial?
8. How can mapping reductions prove nonrecognizability as well as undecidability?