On the previous page, we saw that many questions about machines are decidable — we can build TMs that always halt with the right answer. But we left the TM column of the decidability table full of question marks. Can a TM analyze another TM?
The answer is no — at least not always. This page proves the most important negative result in computer science: there exist problems that no algorithm can ever solve. Not because we haven't been clever enough, but because of a fundamental mathematical impossibility.
The key insight comes from a question of sizes: there are more languages than there are Turing machines. Since each TM can recognize at most one language, some languages must have no TM at all. But we'll go further — we'll exhibit specific, natural problems that are undecidable, starting with \(A_{\text{TM}}\).
\(A_{\text{TM}}\) is Turing-Recognizable
First, the positive result. The acceptance problem for Turing machines is at least recognizable:
$$A_{\text{TM}} = \{\langle M, w \rangle \mid M \text{ is a TM and } M \text{ accepts } w\}$$
Theorem. \(A_{\text{TM}}\) is Turing-recognizable.
Proof — the Universal Turing Machine
\(U = \) "On input \(\langle M, w \rangle\) where \(M\) is a TM and \(w\) is a string:
Simulate \(M\) on input \(w\), step by step.
If \(M\) ever enters \(q_{\text{accept}}\), accept. If \(M\) ever enters \(q_{\text{reject}}\), reject."
This TM \(U\) is called the Universal Turing Machine — it's a TM that can simulate any other TM. It accepts \(\langle M, w \rangle\) exactly when \(M\) accepts \(w\), so \(L(U) = A_{\text{TM}}\).
Why \(U\) is only a recognizer, not a decider: If \(M\) loops on \(w\), then \(U\) also loops — the simulation never reaches \(q_{\text{accept}}\) or \(q_{\text{reject}}\). So \(U\) doesn't halt on all inputs.
The Universal TM is a huge conceptual milestone. It's a single, fixed machine that can run any program — the theoretical foundation for general-purpose computers. Your laptop is essentially a physical realization of \(U\): it takes a program (encoded as a file) and an input, and simulates the program on that input.
A Question of Sizes
Before diving into the specific proof, let's build intuition for why undecidable languages must exist.
How many TMs exist? Countably infinite (\(\aleph_0\)). Every TM can be encoded as a finite string over a fixed alphabet (say, binary). The set of all finite binary strings is countable (list them: \(\varepsilon, 0, 1, 00, 01, 10, 11, 000, \ldots\)). Since each TM has at least one encoding, and each encoding is a finite string, the set of TMs is at most countable. It's exactly countably infinite because there are infinitely many valid TMs.
How many languages exist? Uncountably infinite (\(2^{\aleph_0}\)). A language over \(\Sigma = \{0, 1\}\) is a subset of \(\Sigma^*\). The set of all subsets of a countably infinite set is uncountable — this is Cantor's theorem (\(|\mathcal{P}(S)| > |S|\) for any set \(S\)). Each language corresponds to a unique infinite binary string (its "characteristic sequence": the \(i\)-th bit is 1 iff the \(i\)-th string in lexicographic order is in the language). The set of infinite binary strings is uncountable (same as \(\mathbb{R}\)).
So: countably many TMs, uncountably many languages. Most languages have no TM. The recognizable and decidable languages are a vanishingly small fraction of all languages — a drop in an infinite ocean.
But this is just an existence argument — it says some language is unrecognizable without telling us which one. To find a specific undecidable language, we need diagonalization.
Diagonalization: The Core Technique
Diagonalization was invented by Georg Cantor in 1891 to prove that the real numbers are uncountable. The idea: assume a complete list exists, then construct an element that differs from every item on the list by design. Contradiction — the list wasn't complete.
We'll use the same technique, but instead of real numbers, our "list" is an enumeration of all Turing machines, and we'll construct a language that differs from every TM's language.
The Setup
List all TMs as \(M_1, M_2, M_3, \ldots\) (possible because TMs are countable). List all strings as \(s_1, s_2, s_3, \ldots\) (in lexicographic order). Build an infinite table where entry \((i, j)\) is "accept" if \(M_i\) accepts \(s_j\), and "reject/loop" otherwise:
\(s_1\)
\(s_2\)
\(s_3\)
\(s_4\)
\(\cdots\)
\(M_1\)
acc
acc
acc
rej
\(\cdots\)
\(M_2\)
acc
rej
rej
acc
\(\cdots\)
\(M_3\)
rej
rej
acc
acc
\(\cdots\)
\(M_4\)
acc
acc
rej
rej
\(\cdots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(\ddots\)
Now look at the diagonal — the highlighted entries \((1,1), (2,2), (3,3), (4,4), \ldots\) This is the sequence of "does \(M_i\) accept \(s_i\)?" — does each TM accept its own encoding?
Construct a language \(D\) that flips every diagonal entry: \(s_i \in D\) iff \(M_i\) does NOT accept \(s_i\). In the table above: \(M_1\) accepts \(s_1\), so \(s_1 \notin D\). \(M_2\) rejects \(s_2\), so \(s_2 \in D\). And so on.
The punchline: \(D\) is not recognized by ANY TM in the list. Why? \(D\) differs from \(L(M_i)\) on string \(s_i\) — by construction, \(D\) and \(L(M_i)\) disagree on whether \(s_i\) is a member. Since the list contains all TMs, \(D\) is not Turing-recognizable.
\(A_{\text{TM}}\) is Undecidable
The diagonalization argument above shows that some language is unrecognizable. Now we use the same technique to show that a specific, natural language — \(A_{\text{TM}}\) — is undecidable.
Theorem 4.11 (Sipser). \(A_{\text{TM}}\) is undecidable.
Proof — by contradiction using diagonalization
Assume for contradiction that some TM \(H\) decides \(A_{\text{TM}}\). That is, \(H\) always halts and:
$$H(\langle M, w \rangle) = \begin{cases} \text{accept} & \text{if } M \text{ accepts } w \\ \text{reject} & \text{if } M \text{ does not accept } w \end{cases}$$
Now construct a new TM \(D\) that uses \(H\) as a subroutine:
\(D = \) "On input \(\langle M \rangle\) where \(M\) is a TM:
Run \(H\) on input \(\langle M, \langle M \rangle \rangle\). (Ask: does \(M\) accept its own description?)
If \(H\) accepts, reject. If \(H\) rejects, accept."
In other words, \(D(\langle M \rangle)\) does the opposite of what \(M\) does on its own description.
Now ask: what does \(D\) do on input \(\langle D \rangle\)? That is, we feed \(D\) its own description.
If \(D\) accepts \(\langle D \rangle\): then \(H(\langle D, \langle D \rangle \rangle)\) accepted, meaning \(D\) accepts \(\langle D \rangle\)... but step 2 says \(D\) rejects. Contradiction.
If \(D\) rejects \(\langle D \rangle\): then \(H(\langle D, \langle D \rangle \rangle)\) rejected, meaning \(D\) doesn't accept \(\langle D \rangle\)... but step 2 says \(D\) accepts. Contradiction.
Both cases lead to contradiction. Therefore the assumption that \(H\) exists is false. No TM decides \(A_{\text{TM}}\).
Understanding the self-reference. The key move is feeding \(D\) its own description — this is the "diagonal" part. \(D\) is defined to disagree with whatever \(M\) does on \(\langle M \rangle\). When we plug in \(M = D\), it has to disagree with itself, which is impossible. This is exactly Cantor's diagonalization applied to TMs instead of real numbers.
If this feels like a paradox — it's the same structure as the barber paradox: "The barber shaves everyone who doesn't shave themselves. Does the barber shave himself?" The answer: such a barber can't exist. Here: such a decider \(H\) can't exist.
The Halting Problem
A closely related formulation: instead of asking "does \(M\) accept \(w\)?", ask "does \(M\) halt on \(w\)?"
$$\text{HALT}_{\text{TM}} = \{\langle M, w \rangle \mid M \text{ is a TM and } M \text{ halts on } w\}$$
This is also undecidable. There are two ways to prove it — a direct diagonalization (standalone, not depending on \(A_{\text{TM}}\)) and a reduction from \(A_{\text{TM}}\). The course covers both.
Proof 1: Direct Diagonalization for \(\text{HALT}_{\text{TM}}\)
This proof uses the same self-referential trick as the \(A_{\text{TM}}\) proof, but applied directly to the halting question. It does not assume \(A_{\text{TM}}\) is undecidable — it's a standalone proof.
Proof — direct diagonalization
Assume for contradiction that \(\text{HALT}_{\text{TM}}\) is decidable. Let \(H\) be a decider for \(\text{HALT}_{\text{TM}}\).
Construct TM \(D\):
\(D = \) "On input \(\langle M \rangle\) where \(M\) is a TM:
Run \(H\) on input \(\langle M, \langle M \rangle \rangle\). (Ask: does \(M\) halt on its own description?)
If \(H\) accepts (meaning \(M\) halts on \(\langle M \rangle\)), loop forever.
If \(H\) rejects (meaning \(M\) doesn't halt on \(\langle M \rangle\)), reject (and therefore halt)."
Now run \(D\) on \(\langle D \rangle\):
Case 1: \(H\) accepts (says \(D\) halts on \(\langle D \rangle\)) → \(D\) loops. But then \(D\) does NOT halt on \(\langle D \rangle\) — contradicting \(H\)'s answer.
Case 2: \(H\) rejects (says \(D\) doesn't halt on \(\langle D \rangle\)) → \(D\) rejects (halts). But then \(D\) DOES halt on \(\langle D \rangle\) — contradicting \(H\)'s answer.
Both cases produce contradictions. Therefore \(H\) cannot exist. \(\text{HALT}_{\text{TM}}\) is undecidable.
Compare to the \(A_{\text{TM}}\) diagonalization. The classic \(A_{\text{TM}}\) proof builds \(D\) that flips the accept/reject answer: "if \(H\) says accept, reject; if reject, accept." The \(\text{HALT}_{\text{TM}}\) version flips the halt/loop behavior: "if \(H\) says halts, loop; if doesn't halt, halt." Same structure, different axis of contradiction.
Proof 2: Reduction from \(A_{\text{TM}}\) to \(\text{HALT}_{\text{TM}}\)
If \(\text{HALT}_{\text{TM}}\) were decidable, we could use it to decide \(A_{\text{TM}}\). The key insight: knowing that \(M\) halts on \(w\) makes it safe to simulate \(M\) on \(w\) — we won't get stuck in an infinite loop.
Proof — reduction from \(A_{\text{TM}}\)
Assume for contradiction that \(\text{HALT}_{\text{TM}}\) is decidable. Let \(R\) be a decider for \(\text{HALT}_{\text{TM}}\).
Construct \(S\) that decides \(A_{\text{TM}}\):
\(S = \) "On input \(\langle M, w \rangle\):
Run \(R\) on input \(\langle M, w \rangle\). (Ask: does \(M\) halt on \(w\)?)
If \(R\) rejects, reject. (\(M\) loops on \(w\), so \(M\) certainly doesn't accept \(w\).)
If \(R\) accepts, run \(M\) on \(w\). (Safe! We know \(M\) halts.)
If \(M\) accepts, accept. If \(M\) rejects, reject."
\(S\) always halts: \(R\) always halts (it's a decider), and step 3 only runs \(M\) when \(M\) is guaranteed to halt. \(S\) correctly decides \(A_{\text{TM}}\). But \(A_{\text{TM}}\) is undecidable — contradiction. Therefore \(\text{HALT}_{\text{TM}}\) is undecidable.
Proof 3: Reduction from \(\text{HALT}_{\text{TM}}\) to \(A_{\text{TM}}\)
The reduction also works in the other direction: if \(A_{\text{TM}}\) were decidable, we could use it to decide \(\text{HALT}_{\text{TM}}\). This shows the two problems are interreducible — equally hard.
Proof — reduction from \(\text{HALT}_{\text{TM}}\)
Assume for contradiction that \(A_{\text{TM}}\) is decidable. Let \(H\) be a decider for \(A_{\text{TM}}\).
Construct \(S\) that decides \(\text{HALT}_{\text{TM}}\):
\(S = \) "On input \(\langle M, w \rangle\):
Construct a new TM \(M'\) defined as: \(M' = \) 'On input \(w'\) (ignored): Run \(M\) on \(w\). If \(M\) accepts or rejects, accept.'
Run \(H\) on \(\langle M', \texttt{"hello"} \rangle\).
If \(H\) accepts, accept. If \(H\) rejects, reject."
What is \(M'\)? \(M'\) ignores its own input entirely. It runs \(M\) on the hardcoded \(w\). If \(M\) halts on \(w\) (accept or reject), \(M'\) accepts. If \(M\) loops on \(w\), \(M'\) also loops. So \(M'\) accepts "hello" iff \(M\) halts on \(w\).
Why "hello"? The choice is arbitrary — any fixed string works. \(M'\) ignores its input, so its behavior on "hello" depends only on whether \(M\) halts on \(w\). The silly choice is deliberately memorable.
\(S\) decides \(\text{HALT}_{\text{TM}}\). But \(\text{HALT}_{\text{TM}}\) is undecidable — contradiction. Therefore \(A_{\text{TM}}\) is undecidable.
The \(M'\) construction trick. This is a technique you'll see repeatedly in reduction proofs: build a modified TM that converts one property into another. Here, \(M'\) converts "halting" into "accepting" — it accepts whenever \(M\) halts (regardless of whether \(M\) accepts or rejects). This bridges the gap between the halting problem (does \(M\) halt?) and the acceptance problem (does \(M'\) accept?).
Bidirectional reductions. We've shown \(A_{\text{TM}} \leq \text{HALT}_{\text{TM}}\) (Proof 2) and \(\text{HALT}_{\text{TM}} \leq A_{\text{TM}}\) (Proof 3). Each problem's undecidability implies the other's. They are "equally hard" — interreducible. You can use either as your starting undecidable problem for future reduction proofs.
The halting problem in everyday terms. Can you write a program that takes any program and any input, and correctly determines whether the program will eventually finish? No. This is not an engineering limitation — it's a mathematical impossibility. No amount of computing power, clever algorithms, or AI will ever produce a general halt-checker. This is what undecidability means in practice.
More Undecidable Problems via Reduction
Once we know \(A_{\text{TM}}\) is undecidable, we can prove other problems undecidable by reduction: show that solving the new problem would let us solve \(A_{\text{TM}}\).
\(E_{\text{TM}}\) is Undecidable
$$E_{\text{TM}} = \{\langle M \rangle \mid M \text{ is a TM and } L(M) = \emptyset\}$$
Proof sketch — reduction from \(A_{\text{TM}}\)
Assume \(E_{\text{TM}}\) is decidable by some TM \(R\). We build a decider for \(A_{\text{TM}}\):
\(S = \) "On input \(\langle M, w \rangle\):
Construct a new TM \(M_1\) that does the following: \(M_1 = \) 'On input \(x\): if \(x \neq w\), reject. If \(x = w\), run \(M\) on \(w\) and accept if \(M\) accepts.'
Run \(R\) on \(\langle M_1 \rangle\).
If \(R\) rejects (meaning \(L(M_1) \neq \emptyset\), meaning \(M\) accepts \(w\)), then accept. If \(R\) accepts (meaning \(L(M_1) = \emptyset\), meaning \(M\) doesn't accept \(w\)), then reject."
The trick: \(M_1\) is designed so that \(L(M_1) = \{w\}\) if \(M\) accepts \(w\), and \(L(M_1) = \emptyset\) otherwise. So testing emptiness of \(M_1\) tells us whether \(M\) accepts \(w\). This decides \(A_{\text{TM}}\) — contradiction.
\(ALL_{\text{TM}}\) is Undecidable
$$ALL_{\text{TM}} = \{\langle M \rangle \mid M \text{ is a TM and } L(M) = \Sigma^*\}$$
Proof sketch — reduction from \(A_{\text{TM}}\)
Assume \(ALL_{\text{TM}}\) is decidable by some TM \(R\). We build a decider for \(A_{\text{TM}}\):
\(S = \) "On input \(\langle M, w \rangle\):
Construct a new TM \(M'\) defined as: \(M' = \) 'On input \(x\): Run \(M\) on \(w\). If \(M\) accepts \(w\), accept \(x\). Otherwise, reject \(x\).'
Run \(R\) on \(\langle M' \rangle\).
If \(R\) accepts (meaning \(L(M') = \Sigma^*\)), accept. If \(R\) rejects, reject."
The trick: \(M'\) ignores its own input \(x\). If \(M\) accepts \(w\), then \(M'\) accepts everything — \(L(M') = \Sigma^*\). If \(M\) doesn't accept \(w\), then \(M'\) accepts nothing or loops — \(L(M') \neq \Sigma^*\). So testing universality of \(M'\) tells us whether \(M\) accepts \(w\). This decides \(A_{\text{TM}}\) — contradiction.
If we could decide \(EQ_{\text{TM}}\), we could decide \(E_{\text{TM}}\): given \(\langle M \rangle\), construct a TM \(M_{\emptyset}\) that rejects everything (\(L(M_{\emptyset}) = \emptyset\)). Then ask \(EQ_{\text{TM}}\): is \(L(M) = L(M_{\emptyset})\)? This tells us whether \(L(M) = \emptyset\). But \(E_{\text{TM}}\) is undecidable — contradiction.
The reduction proof pattern. Every undecidability proof by reduction follows the same structure:
Assume the target problem \(B\) is decidable, with decider \(R\).
Construct a machine \(S\) that uses \(R\) to decide a known undecidable problem \(A\).
\(A\) is undecidable — contradiction.
Therefore \(B\) is undecidable.
The creative step is always step 2: building the right modified TM (\(M_1\), \(M'\), etc.) that transforms the question about \(A\) into a question about \(B\).
Recognizable vs. Co-Recognizable
The undecidability of \(A_{\text{TM}}\) lets us fill in more of the picture. We already know \(A_{\text{TM}}\) is recognizable (the universal TM). What about its complement?
Corollary (Sipser 4.22). \(\overline{A_{\text{TM}}}\) is NOT Turing-recognizable.
Proof — from the complement theorem
By Theorem 4.22 (previous page): a language is decidable iff both it and its complement are recognizable.
We know: \(A_{\text{TM}}\) is recognizable, \(A_{\text{TM}}\) is NOT decidable.
If \(\overline{A_{\text{TM}}}\) were also recognizable, then both \(A_{\text{TM}}\) and \(\overline{A_{\text{TM}}}\) would be recognizable, making \(A_{\text{TM}}\) decidable — contradiction. So \(\overline{A_{\text{TM}}}\) is not recognizable.
This gives us a concrete example for each zone of the language hierarchy:
Both \(L\) and \(\overline{L}\) are unrecognizable
\(EQ_{\text{TM}}\)
The Complete Decidability Table
We can now fill in the TM column that was left with question marks on the previous page:
DFA
NFA
RegEx
CFG
PDA
TM
\(A\)
Yes
Yes
Yes
Yes
Yes
No
\(E\)
Yes
Yes
Yes
Yes
Yes
No
\(ALL\)
Yes
Yes
Yes
No
No
No
\(EQ\)
Yes
Yes
Yes
No
No
No
The pattern. Reading left to right: DFA/NFA/RegEx are fully decidable. CFG/PDA lose \(ALL\) and \(EQ\). TMs lose everything — not a single problem is decidable. As computational models get more powerful, it becomes harder to answer questions about them. The most powerful model (TMs) is the hardest to reason about. There's a deep irony: the machine that can compute the most is the one we can say the least about.
Reductions: Direct vs. Mapping
All the undecidability proofs above use direct reductions (also called "Turing reductions" informally): assume a decider for \(B\) exists, use it as a subroutine to build a machine that decides \(A\) (known undecidable), derive contradiction. This is powerful but informal — the reduction is embedded in the proof argument.
There is a more formal and structured alternative: mapping reductions. These are explicit computable functions that transform inputs, and they can prove not just undecidability but also (non-)recognizability.
Direct Reductions
This is what we've been doing in all the proofs above. The pattern:
Direct reduction pattern
Assume \(B\) is decidable, with decider \(R\).
Construct a TM \(S\) that uses \(R\) as a subroutine — calling it, inspecting its answer, doing additional computation — to decide \(A\) (known undecidable).
\(A\) is undecidable → contradiction → \(B\) is undecidable.
Key feature: \(S\) can use \(R\) as an oracle — call it multiple times, in arbitrary ways, with constructed inputs. The reduction is implicit, embedded in the proof-by-contradiction argument.
Mapping Reductions
Definition. Language \(A\) is mapping reducible to language \(B\) (written \(A \leq_m B\)) if there exists a computable function \(f: \Sigma^* \to \Sigma^*\) such that for every \(w\):
$$w \in A \iff f(w) \in B$$
The function \(f\) must be computed by a TM that always halts (a total computable function). \(f\) simply transforms inputs — it does not use a decider for \(B\).
If \(A \leq_m B\) and \(B\) is decidable, then \(A\) is decidable: just compute \(f(w)\) and run the decider for \(B\) on \(f(w)\). Contrapositive: if \(A\) is undecidable and \(A \leq_m B\), then \(B\) is undecidable.
Why Mapping Reductions Are Stronger
Mapping reductions are more restrictive than direct reductions (no oracle access), but this restriction gives them extra power: they can prove recognizability and co-recognizability properties, not just decidability.
Aspect
Direct Reduction
Mapping Reduction
Mechanism
Assume decider, derive contradiction
Computable function \(f: \Sigma^* \to \Sigma^*\)
Uses a decider?
Yes (hypothetical subroutine)
No
Input/Output
Takes input, uses oracle, decides
Takes input, produces transformed input
Can prove
Undecidability only
Undecidability + (non-)recognizability
Notation
"A reduces to B" (informal)
\(A \leq_m B\) (formal)
Because mapping reductions preserve membership in both directions (\(w \in A \iff f(w) \in B\)), they transfer recognizability: if \(A\) is not recognizable and \(A \leq_m B\), then \(B\) is not recognizable either.
Example: A Mapping Reduction from \(E_{\text{CFG}}\)
Here's a concrete mapping reduction function — no hypothetical decider, just a computable transformation:
Mapping reduction function \(F\)
\(F = \) "On input \(\langle G \rangle\) where \(G\) is a CFG:
Convert \(G\) to Chomsky Normal Form → \(G' = (V', \Sigma', R', S')\).
What \(F\) does: \(L(G'') = L(G) \cup \{x\}\). Since \(x\) is a fresh symbol not in the original alphabet, \(G''\) always generates at least one string (\(x\)).
If \(L(G) = \emptyset\): \(L(G'') = \{x\}\) — exactly one string.
If \(L(G) \neq \emptyset\): \(L(G'') = L(G) \cup \{x\}\) — at least two strings (something from \(L(G)\) plus \(x\)).
So: \(G \in E_{\text{CFG}} \iff |L(G'')| = 1\). This is a mapping reduction from \(E_{\text{CFG}}\) to the "singleton language" problem \(\{\langle G \rangle \mid |L(G)| = 1\}\), proving it undecidable.
Note: \(F\) is a standalone computable function. It doesn't call any decider. It simply transforms the input encoding — CNF conversion always terminates, choosing a fresh symbol is mechanical, and writing the output is mechanical.
\(EQ_{\text{TM}}\) is Neither Recognizable Nor Co-Recognizable
Mapping reductions let us prove something direct reductions cannot: that \(EQ_{\text{TM}}\) sits completely outside both the recognizable and co-recognizable classes.
Proof sketch — \(EQ_{\text{TM}}\) is not recognizable
We show \(\overline{A_{\text{TM}}} \leq_m EQ_{\text{TM}}\) via a mapping reduction. Since \(\overline{A_{\text{TM}}}\) is not recognizable, \(EQ_{\text{TM}}\) isn't either.
Given \(\langle M, w \rangle\), construct two TMs:
\(M_1\) = TM that rejects everything (\(L(M_1) = \emptyset\)).
\(M_2\) = TM that ignores its input, runs \(M\) on \(w\), and accepts if \(M\) accepts.
Then \(L(M_1) = L(M_2)\) iff \(L(M_2) = \emptyset\) iff \(M\) does not accept \(w\) iff \(\langle M, w \rangle \in \overline{A_{\text{TM}}}\).
So \(\langle M, w \rangle \in \overline{A_{\text{TM}}} \iff \langle M_1, M_2 \rangle \in EQ_{\text{TM}}\). This gives \(\overline{A_{\text{TM}}} \leq_m EQ_{\text{TM}}\).
Proof sketch — \(EQ_{\text{TM}}\) is not co-recognizable
We show \(\overline{A_{\text{TM}}} \leq_m \overline{EQ_{\text{TM}}}\). Since \(\overline{A_{\text{TM}}}\) is not recognizable, \(\overline{EQ_{\text{TM}}}\) isn't either — meaning \(EQ_{\text{TM}}\) is not co-recognizable.
Given \(\langle M, w \rangle\), construct:
\(M_1\) = TM that accepts everything (\(L(M_1) = \Sigma^*\)).
\(M_2\) = TM that ignores its input, runs \(M\) on \(w\), and accepts if \(M\) accepts.
Then \(L(M_1) = L(M_2)\) iff \(L(M_2) = \Sigma^*\) iff \(M\) accepts \(w\) iff \(\langle M, w \rangle \in A_{\text{TM}}\).
So \(\langle M, w \rangle \in A_{\text{TM}} \iff \langle M_1, M_2 \rangle \in EQ_{\text{TM}}\), which means \(\langle M, w \rangle \in \overline{A_{\text{TM}}} \iff \langle M_1, M_2 \rangle \in \overline{EQ_{\text{TM}}}\).
\(EQ_{\text{TM}}\) — the "hardest" problem. Not decidable, not recognizable, not co-recognizable. It sits completely outside every computability class except "all languages." You can't even build a TM that partially answers this question (no recognizer for either \(EQ_{\text{TM}}\) or its complement). This is the strongest possible negative result in the computability hierarchy.
Full Language Analysis
The exam may ask you to fully classify a language: determine whether it is decidable, recognizable, and co-recognizable. This requires three separate arguments. Here's the systematic approach, demonstrated with a worked example from the lectures.
The three-part analysis pattern:
Decidable? Try to find a reduction from a known undecidable problem. If the reduction works, the language is not decidable.
Co-recognizable? Try to build a recognizer for the complement. The key technique is dovetailing — simulate on increasingly many inputs for increasingly many steps, avoiding getting stuck on any one computation.
Recognizable? Use the theorem: if the language is co-recognizable and not decidable, then it cannot be recognizable (because recognizable + co-recognizable = decidable).
Worked Example: \(L = \{\langle M, n \rangle \mid L(M) \subseteq \{a^m \mid m < n\}\}\)
\(L\) contains pairs \(\langle M, n \rangle\) where \(M\) is a TM over the unary alphabet \(\{a\}\) and \(M\)'s language is a subset of the finite set \(\{\varepsilon, a, aa, \ldots, a^{n-1}\}\) — i.e., \(M\) only accepts strings shorter than \(n\).
Step 1 — \(L\) is not decidable (reduction from \(E_{\text{TM}}\))
Assume \(L\) is decidable with decider \(R\). Construct a decider \(S\) for \(E_{\text{TM}}\) (restricted to unary-alphabet TMs):
\(S = \) "On input \(\langle M \rangle\):
Run \(R\) on \(\langle M, 0 \rangle\).
If \(R\) accepts, accept. Otherwise, reject."
When \(n = 0\): \(\{a^m \mid m < 0\} = \emptyset\), so \(L(M) \subseteq \emptyset\) means \(L(M) = \emptyset\). Thus \(S\) decides \(E_{\text{TM}}\) — but \(E_{\text{TM}}\) is undecidable. Contradiction. \(L\) is not decidable.
Step 2 — \(L\) is co-recognizable (recognizer for \(\overline{L}\))
\(\langle M, n \rangle \in \overline{L}\) means \(M\) accepts some \(a^m\) with \(m \geq n\). We build a recognizer for \(\overline{L}\) using dovetailing:
"On input \(\langle M, n \rangle\):
For \(i = 1, 2, 3, \ldots\):
Run \(M\) for \(i\) steps on each of \(a^n, a^{n+1}, \ldots, a^{n+i}\).
If \(M\) accepts any of these inputs, accept."
If \(\langle M, n \rangle \in \overline{L}\): some \(a^m\) with \(m \geq n\) is accepted by \(M\) in finitely many steps \(k\). When \(i \geq \max(k, m - n)\), we'll catch it. So the recognizer eventually accepts.
If \(\langle M, n \rangle \in L\): \(M\) never accepts any such string, so the recognizer loops forever. This is fine — recognizers may loop on non-members.
\(\overline{L}\) is recognizable → \(L\) is co-recognizable.
Step 3 — \(L\) is not recognizable
We've shown: \(L\) is co-recognizable (Step 2) and \(L\) is not decidable (Step 1).
By the theorem: \(L\) is decidable iff \(L\) is recognizable AND co-recognizable.
If \(L\) were recognizable, then \(L\) would be recognizable + co-recognizable = decidable. But \(L\) is not decidable. Therefore \(L\) is not recognizable.
Property
Answer
Decidable?
No — reduces from \(E_{\text{TM}}\)
Recognizable?
No — would force decidability (since co-recognizable)
Co-recognizable?
Yes — dovetailing recognizer for \(\overline{L}\)
Dovetailing — the technique. When you need to search an infinite space without getting stuck, dovetail: incrementally increase both the set of inputs tested and the number of simulation steps per input. This ensures you never spend infinite time on any single input. You'll see this technique whenever a recognizer needs to search over multiple TM computations.
Exercises
Exercise 1: Trace the Diagonalization
Suppose we have three TMs and three strings with the following behavior:
\(s_1\)
\(s_2\)
\(s_3\)
\(M_1\)
accept
reject
accept
\(M_2\)
accept
accept
reject
\(M_3\)
reject
reject
accept
(a) What is the diagonal? (b) What is the "anti-diagonal" language \(D\)? (c) Verify that \(D \neq L(M_i)\) for each \(i\).
(a) Diagonal: (M1, s1) = accept, (M2, s2) = accept, (M3, s3) = accept.
(b) Anti-diagonal D: Flip each: s1 -> reject, s2 -> reject, s3 -> reject.
So D = {} (the empty set — D contains none of the three strings).
(c) Verify:
- D vs L(M1) = {s1, s3}: D disagrees on s1 (M1 accepts s1, D doesn't). Confirmed different.
- D vs L(M2) = {s1, s2}: D disagrees on s2 (M2 accepts s2, D doesn't). Confirmed different.
- D vs L(M3) = {s3}: D disagrees on s3 (M3 accepts s3, D doesn't). Confirmed different.
D differs from each L(Mi) on exactly the diagonal entry — by construction.
Exercise 2: The D Machine Paradox
In the proof that \(A_{\text{TM}}\) is undecidable, we built \(D\) that does the opposite of what \(M\) does on \(\langle M \rangle\). Walk through what happens when we run \(D\) on \(\langle D \rangle\), assuming \(H\) (the hypothetical decider) says "accept." Now repeat assuming \(H\) says "reject." Why can't \(H\) give either answer?
Case 1: H says "accept" (meaning H thinks D accepts ⟨D⟩)
- D receives ⟨D⟩, runs H(⟨D, ⟨D⟩⟩)
- H returns "accept"
- D does the OPPOSITE: D rejects
- But H said D accepts ⟨D⟩! Contradiction — D actually rejects.
Case 2: H says "reject" (meaning H thinks D does not accept ⟨D⟩)
- D receives ⟨D⟩, runs H(⟨D, ⟨D⟩⟩)
- H returns "reject"
- D does the OPPOSITE: D accepts
- But H said D doesn't accept ⟨D⟩! Contradiction — D actually accepts.
H can't say "accept" (leads to D rejecting) and can't say "reject" (leads to D accepting). There is no correct answer for H to give. Since H is supposed to be a decider (always halts with the right answer), and there is no right answer it can give on this input, H cannot exist.
The self-reference is essential: if we ran D on some other machine's encoding, there'd be no paradox. It's only when we feed D its own encoding that the "do the opposite" instruction becomes self-contradictory.
Exercise 3: Recognizability Classification
For each language, determine whether it is (a) decidable, (b) recognizable but not decidable, (c) co-recognizable but not recognizable, or (d) neither recognizable nor co-recognizable.
\(A_{\text{DFA}}\)
\(A_{\text{TM}}\)
\(\overline{A_{\text{TM}}}\)
\(E_{\text{TM}}\)
\(EQ_{\text{DFA}}\)
1. A_DFA: (a) Decidable. Simulate the DFA on w — always halts.
2. A_TM: (b) Recognizable but not decidable. The universal TM recognizes it. Undecidable by diagonalization.
3. complement of A_TM: (c) Co-recognizable but not recognizable. Its complement (A_TM) is recognizable, making it co-recognizable. If it were also recognizable, A_TM would be decidable — contradiction.
4. E_TM: (c) Co-recognizable but not recognizable. The complement of E_TM (i.e., "L(M) is nonempty") is recognizable: enumerate all strings, simulate M on each, accept if M accepts any. But E_TM itself is not recognizable (proven via reduction).
5. EQ_DFA: (a) Decidable. Build the symmetric-difference DFA and test for emptiness — always halts.
Exercise 4: Trace the HALT_TM Diagonalization
In the direct diagonalization proof for \(\text{HALT}_{\text{TM}}\), we built \(D\) that loops when \(H\) says "halts" and halts when \(H\) says "doesn't halt." Walk through both cases when \(D\) is run on \(\langle D \rangle\). Fill in the table:
\(H\) says about \(D(\langle D \rangle)\)
\(D\) does
\(D\) actually halts?
Contradiction?
"halts"
?
?
?
"doesn't halt"
?
?
?
H says about D(⟨D⟩)
D does
D actually halts?
Contradiction?
"halts" (accept)
Loop
No — D loops
YES: H said halts, but D loops
"doesn't halt" (reject)
Reject (halt)
Yes — D halts
YES: H said doesn't halt, but D halts
Both rows contradict. H cannot exist. HALT_TM is undecidable.
Compare to the A_TM version: In the A_TM proof, D flips accept/reject. Here, D flips halt/loop. Same self-referential structure, different axis.
Exercise 5: Full Language Analysis
Classify \(L = \{\langle M, k \rangle \mid M \text{ is a TM that accepts at least } k \text{ words of length} \geq k\}\).
Determine whether \(L\) is (i) decidable, (ii) recognizable, and (iii) co-recognizable.
Hint: For recognizability, think dovetailing. For decidability, think about whether the property is non-trivial (Rice's theorem or direct reduction). For co-recognizability, think about what the complement requires you to verify.
(i) Decidable? No.
"Accepts at least k words of length ≥ k" is a non-trivial semantic property of TMs. By Rice's theorem (or a direct reduction from A_TM), it is undecidable. Sketch: if k = 1, the question becomes "does M accept at least one word of length ≥ 1?", which is close to the complement of E_TM. A reduction from A_TM can be constructed by building a TM M' that, given ⟨M, w⟩, accepts k long strings iff M accepts w.
(ii) Recognizable? Yes.
To recognize L, dovetail: simulate M on all strings of length ≥ k in parallel (increasing the step count and input set over time). Count how many distinct strings M accepts. If the count reaches k, accept. If M does accept ≥ k such words, each accepting computation is finite, so the dovetailing will eventually find all k of them. If not, the recognizer loops — which is fine.
(iii) Co-recognizable? No.
The complement says "M accepts fewer than k words of length ≥ k." Verifying this requires knowing that M does NOT accept certain strings — but M might loop on them, and you can never be sure a looping computation won't eventually accept. You'd need to verify non-acceptance on infinitely many inputs, which is exactly the kind of property that can't be recognized. Since L is recognizable but not decidable, L is not co-recognizable (by the theorem: decidable iff recognizable + co-recognizable).
Summary: L is recognizable but neither decidable nor co-recognizable.
Exercise 6: Reduction Direction
In the reduction from \(A_{\text{TM}}\) to \(\text{HALT}_{\text{TM}}\), we showed: "if HALT_TM is decidable, then A_TM is decidable." In the reduction from \(\text{HALT}_{\text{TM}}\) to \(A_{\text{TM}}\), we showed the reverse. Does this mean A_TM and HALT_TM are "equally difficult"? Can you always reduce in both directions between undecidable problems?
Yes, A_TM and HALT_TM are interreducible — each reduces to the other. This means they are "equally hard" in the sense that solving either one would solve both.
No, you cannot always reduce in both directions. Some undecidable problems are "harder" than others. For example, EQ_TM is undecidable AND neither recognizable nor co-recognizable, while A_TM is undecidable but still recognizable. You can reduce A_TM to EQ_TM (via mapping reduction), but the reverse direction doesn't work for mapping reductions — A_TM is recognizable, and mapping reductions preserve recognizability, so if EQ_TM ≤_m A_TM then EQ_TM would be recognizable (which it isn't).
This is why mapping reductions are useful: they reveal a finer structure within the undecidable problems, distinguishing "merely undecidable" from "not even recognizable."
Summary
Undecidability & Reductions — the essentials:
\(A_{\text{TM}}\) is recognizable: the Universal TM simulates any TM on any input (but may loop)
\(A_{\text{TM}}\) is undecidable: diagonalization — assume a decider \(H\), build \(D\) that does the opposite on its own encoding, get contradiction
The size argument: countably many TMs, uncountably many languages — most languages have no TM
Diagonalization technique: list all items, construct something that differs from every item on the list (same as Cantor's proof for reals)
The halting problem: "does \(M\) halt on \(w\)?" is undecidable — provable by direct diagonalization (standalone) or by reduction from \(A_{\text{TM}}\)
Bidirectional reductions: \(A_{\text{TM}}\) and \(\text{HALT}_{\text{TM}}\) reduce to each other — they are interreducible and equally hard
The \(M'\) trick: constructing modified TMs that convert one property into another (e.g., halting → accepting) — the key technique in reduction proofs
Proving undecidability via reduction: assume \(B\) decidable → build machine that decides \(A\) (undecidable) → contradiction → \(B\) undecidable. Used for \(\text{HALT}_{\text{TM}}\), \(E_{\text{TM}}\), \(ALL_{\text{TM}}\), \(EQ_{\text{TM}}\)
\(\overline{A_{\text{TM}}}\) is not recognizable: because \(A_{\text{TM}}\) is recognizable + undecidable, the complement can't be recognizable (by Theorem 4.22)
Complete TM column: all four problems (\(A, E, ALL, EQ\)) are undecidable for TMs
Direct vs. mapping reductions: direct reductions use a hypothetical decider as a subroutine (prove undecidability only); mapping reductions are computable functions \(f\) with \(w \in A \iff f(w) \in B\) (prove undecidability + (non-)recognizability)
\(EQ_{\text{TM}}\): neither recognizable nor co-recognizable — the strongest negative result, proven via mapping reductions from \(\overline{A_{\text{TM}}}\)
Full language analysis: (1) decidability via reduction, (2) co-recognizability via dovetailing recognizer for complement, (3) recognizability via the theorem (co-recognizable + not decidable → not recognizable)
Dovetailing: simulate on increasingly many inputs for increasingly many steps — the key technique for building recognizers that search infinite spaces