Undecidability

Infinity, diagonalization, and the limits of algorithms

The first fundamental limit

The Turing-machine acceptance problem is

\[ A_{TM} = \{\langle M,w\rangle:M\text{ is a Turing machine that accepts }w\}. \]

A universal Turing machine can recognize this language: simulate \(M\) on \(w\) and accept if the simulation accepts.

If \(M\) accepts \(w\), the simulator eventually accepts.
If \(M\) rejects \(w\), the simulator can reject.
If \(M\) loops on \(w\), the simulator also loops.

Therefore,

\[ A_{TM}\in\mathrm{RECOGNIZABLE}. \]

The central result of this section is stronger:

Theorem. \(A_{TM}\) is undecidable.

No algorithm can always determine whether an arbitrary Turing machine accepts an arbitrary input.

The universal machine recognizes \(A_{TM}\), but recognition does not guarantee termination on negative instances.

Under the Church–Turing thesis, proving that no TM decides \(A_{TM}\) means that no algorithm in any ordinary programming language solves it.

Preparing for diagonalization

The proof resembles Cantor’s proof that some infinite sets cannot be listed. We therefore begin by distinguishing two sizes of infinity.

Countable and Uncountable Sets

Countability

A set is countably infinite if its elements can be placed in a one-to-one correspondence with the positive integers:

\[ 1,2,3,\ldots \]

A set is at most countable if it is finite or countably infinite. Texts sometimes use “countable” for this broader category.

Operationally, a set is at most countable when its members can be arranged in a finite or infinite list in which every member appears at some finite position.

An infinite set that cannot be listed this way is uncountable.

Countable and uncountable sets represent genuinely different sizes of infinity.

Even numbers, integers, and pairs

The positive even numbers are countable because

\[ n\longleftrightarrow2n \]

is a bijection from the positive integers to the positive evens.

The integers are also countable. One possible listing is

\[ 0,1,-1,2,-2,3,-3,\ldots \]

Listings show that the even numbers and all integers are countable.

The set \(\mathbb{N}\times\mathbb{N}\) is countable as well. Arrange pairs \((i,j)\) in a grid and enumerate them along diagonals of constant \(i+j\).

One pairing function is

\[ \pi(i,j) = \frac{(i+j-1)(i+j-2)}{2}+i, \]

for positive integers \(i\) and \(j\).

Diagonal traversal gives every ordered pair a finite position.

Every rational number can be represented by an integer pair \((p,q)\) with \(q\ne0\). Removing duplicate representations still leaves a countable set, so \(\mathbb{Q}\) is countable.

Turing machines are countable

Every Turing machine has a finite description over a finite alphabet. Therefore each machine can be encoded as a finite binary string.

The set of all finite binary strings is countable:

\[ \varepsilon,0,1,00,01,10,11,000,\ldots \]

Some strings are not valid TM encodings, but a subset of a countable set is at most countable. Hence the set of all Turing machines is countable, and we may conceptually list them:

\[ M_1,M_2,M_3,\ldots \]

Cantor’s Diagonal Argument

The real numbers are uncountable

Assume, for contradiction, that all infinite decimal sequences can be listed:

\[ r_1,r_2,r_3,\ldots \]

Construct a new sequence \(x\) by changing the \(n\)th digit of \(r_n\). For example, choose

\[ x_n= \begin{cases} 1,&\text{if the }n\text{th digit of }r_n\ne1,\\ 2,&\text{if the }n\text{th digit of }r_n=1. \end{cases} \]

Then \(x\) differs from \(r_n\) in position \(n\), so \(x\ne r_n\) for every \(n\). The supposedly complete list omits \(x\), a contradiction.

Using digits 1 and 2 avoids the ambiguity caused by decimal representations such as \(0.4999\ldots=0.5000\ldots\).

A diagonal construction creates a real number missing from any proposed list.

Infinite binary strings are uncountable

The same argument applies more cleanly to infinite binary sequences. Suppose they are listed as rows

\[ s_1,s_2,s_3,\ldots \]

Define \(d\) by flipping the diagonal bit:

\[ d_n=1-(s_n)_n. \]

Then \(d\) differs from \(s_n\) at bit \(n\), so it is absent from the list. Therefore, the set of infinite binary sequences is uncountable.

An infinite bit string constructed from the flipped diagonal cannot appear in the proposed list.

The set of all languages is uncountable

Fix an ordering of finite binary strings:

\[ s_1,s_2,s_3,\ldots \]

Every language \(L\subseteq\{0,1\}^*\) has a characteristic sequence

\[ \chi_L=b_1b_2b_3\cdots, \]

where

\[ b_i= \begin{cases} 1,&s_i\in L,\\ 0,&s_i\notin L. \end{cases} \]

Every infinite binary sequence defines one language, and every language defines one infinite binary sequence. Thus

\[ \mathcal{P}(\{0,1\}^*) \]

is uncountable even though \(\{0,1\}^*\) itself is countable.

The counting consequence

There are countably many Turing machines but uncountably many languages. Each TM recognizes at most one language, so:

Most languages are not Turing-recognizable.

This proves that nonrecognizable languages exist. It does not yet establish that the specific language \(A_{TM}\) is undecidable. For that, we use a direct diagonal construction involving machines running on their own encodings.

The Undecidability of (A_{TM})

Separate the recognizer from the hypothetical decider

Let \(U\) be the actual universal recognizer. On input \(\langle M,w\rangle\), it simulates \(M\) on \(w\) and may loop when \(M\) does not accept.

For the proof, assume that a different machine \(H\) decides \(A_{TM}\). Thus \(H\) always halts and satisfies

\[ H(\langle M,w\rangle)= \begin{cases} \text{accept},&M\text{ accepts }w,\\ \text{reject},&M\text{ does not accept }w. \end{cases} \]

“Does not accept” includes both rejecting and looping.

The contradiction begins by assuming a machine can always determine whether \(M\) accepts \(w\).

Construct the diagonal machine

Using \(H\), construct a new TM \(D\) whose input is an encoded Turing machine \(\langle M\rangle\).

D(<M>):
    Run H on <M, <M>>.
    If H accepts, reject.
    If H rejects, accept.

Because \(H\) is assumed to halt on every input, \(D\) also halts on every valid encoding.

The behavior of \(D\) is

\[ D(\langle M\rangle)= \begin{cases} \text{reject},&M\text{ accepts }\langle M\rangle,\\ \text{accept},&M\text{ does not accept }\langle M\rangle. \end{cases} \]

The machine disagrees with each \(M\) on the diagonal case in which \(M\) receives its own encoding.

The diagonal machine runs a machine on its own encoding and reverses the hypothetical decider’s answer.

Run (D) on itself

Now ask what happens on input \(\langle D\rangle\).

Case 1: (D) accepts (D)

Then \(H\) reports that \(D\) accepts \(\langle D\rangle\). By \(D\)’s definition, \(D\) reverses that answer and rejects. Contradiction.

Case 2: (D) rejects (D)

Then \(H\) reports that \(D\) does not accept \(\langle D\rangle\). By \(D\)’s definition, \(D\) reverses that answer and accepts. Contradiction.

In compact form,

\[ D(\langle D\rangle)\text{ accepts} \iff D(\langle D\rangle)\text{ does not accept}. \]

Both possible outcomes contradict themselves. Therefore the assumed decider \(H\) cannot exist.

Conclusion: \(A_{TM}\) is undecidable. \(\square\)

The diagonal entry for \(D\) cannot consistently be labeled yes or no.

Where the contradiction comes from

The proof combines three ingredients:

Machines can be encoded as strings, so a machine may receive a machine description as input.
A universal machine can simulate encoded machines.
Self-reference plus negation creates a computation that disagrees with the supposed decider on its own diagonal entry.

This is the computational counterpart of Cantor’s method: construct an object that differs from every listed object in its own diagonal position.

The proof does not rely on limited time or memory. It rules out a correct, always-halting algorithm even with unlimited resources.

The Hierarchy of Language Classes

The language classes studied so far fit into strict containments:

\[ \mathrm{FINITE} \subsetneq \mathrm{REGULAR} \subsetneq \mathrm{DCFL} \subsetneq \mathrm{CFL} \subsetneq \mathrm{DECIDABLE} \subsetneq \mathrm{RECOGNIZABLE} \subsetneq \mathrm{ALL\ LANGUAGES}. \]

The hierarchy extends beyond recognizable languages to languages no Turing machine can recognize.

Representative examples include:

Class or separation	Example
Finite	\(\{0,11\}\)
Regular but infinite	\(0^*\)
DCFL but nonregular	\(\{a^nb^n:n\ge0\}\)
CFL but not DCFL	Some inherently nondeterministic CFLs
Decidable but not CFL	\(\{a^nb^nc^n:n\ge0\}\)
Recognizable but undecidable	\(A_{TM}\)
Not recognizable	\(\overline{A_{TM}}\) and many others

The counting argument shows that unrecognizable languages are not rare: uncountably many exist, while only countably many languages are recognizable.

Complements and Recognizability

Decidable languages are closed under complement

If \(D\) decides \(L\), construct a decider for \(\overline{L}\) by swapping \(D\)’s accept and reject outcomes. Because \(D\) always halts, the new machine also always halts.

Thus,

\[ L\text{ decidable} \Longrightarrow \overline{L}\text{ decidable}. \]

Recognizable on both sides implies decidable

Theorem. A language \(L\) is decidable if and only if both \(L\) and \(\overline{L}\) are Turing-recognizable.

The forward direction follows from closure of decidable languages under complement.

For the reverse direction, suppose \(M_1\) recognizes \(L\) and \(M_2\) recognizes \(\overline{L}\). On input \(w\), dovetail the two simulations:

run one step of \(M_1(w)\);
run one step of \(M_2(w)\);
continue alternating;
accept if \(M_1\) accepts; and
reject if \(M_2\) accepts.

Every string belongs to exactly one of \(L\) and \(\overline{L}\), so one recognizer must eventually accept. The combined machine always halts and decides \(L\).

Why () is not recognizable

We know that \(A_{TM}\) is recognizable but not decidable. If \(\overline{A_{TM}}\) were also recognizable, the theorem above would make \(A_{TM}\) decidable—a contradiction. Therefore,

\[ \overline{A_{TM}} \notin \mathrm{RECOGNIZABLE}. \]

The complement is

\[ \overline{A_{TM}} = \{\langle M,w\rangle:M\text{ does not accept }w\}, \]

with the chosen convention for malformed encodings. “Does not accept” includes both machines that reject and machines that run forever.

Recognizability is not closed under complement; otherwise recognizable languages would all be decidable.

Three possible classifications

For a decision problem, distinguish:

Decidable: membership and nonmembership can both be confirmed algorithmically.
Recognizable but undecidable: membership can be confirmed, but a nonmember may cause endless search.
Unrecognizable: even membership cannot always be confirmed by a TM.

This hierarchy is more informative than simply labeling problems “solvable” or “unsolvable.”

Common misconceptions

“The simulator might loop, so the problem is undecidable.” One failed strategy is not a proof. The diagonal argument rules out every possible decider.
“Undecidable means every instance is difficult.” Many individual instances are easy. Undecidability means no single algorithm correctly resolves all instances.
“Undecidable means unrecognizable.” \(A_{TM}\) is recognizable but undecidable.
“Unlimited time would solve it.” The obstacle is not a large finite running time. Some simulations never halt.
“Countability alone proves \(A_{TM}\) undecidable.” Counting proves that some languages are unrecognizable. The self-referential proof establishes the specific result for \(A_{TM}\).

Check your understanding

Why is the set of Turing machines countable?
Why is the set of languages over \(\{0,1\}\) uncountable?
What is the role of the diagonal bit in Cantor’s argument?
Why should the hypothetical decider be distinguished from the universal recognizer?
What exactly does \(D\) do on input \(\langle M\rangle\)?
Why does evaluating \(D(\langle D\rangle)\) force a contradiction?
Why does the proof establish impossibility rather than merely inefficiency?
Why would recognizability of both \(A_{TM}\) and its complement imply decidability?