Decidability — decidable (recursive) and recognizable (recursively enumerable) languages: Worked examples

Before we start, one picture to fix the vocabulary we will reuse in every single example.

The scenario matrix

Every language falls into one of these case classes. Each row is a different combination of "how does the machine behave on members?" and "how does it behave on non-members?", plus the degenerate and limiting edges.

Cell	Case class	On members	On non-members	Verdict we expect
C1	Bounded simulation (no loop possible)	halts-accept	halts-reject	decidable
C2	Unbounded simulation, one-sided	halts-accept	may loop	recognizable, undecidable
C3	Complement of a decidable set	halts-reject→accept	halts-accept→reject	decidable (swap trick)
C4	Complement of a "loops-on-no" set	—	—	not recognizable
C5	Both $L$ and $\overline{L}$ recognizable	accept	accept (other machine)	decidable (dovetail)
C6	Degenerate: $L = \emptyset$ or $L = Σ^{*}$	trivial	trivial	decidable
C7	Limiting: input where the machine does loop	—	loops	shows recognizer $\neq =$ decider
C8	Real-world word problem	halts-accept	halts-reject	decidable
C9	Exam twist: "undecidable ⇒ not recognizable?"	—	—	false — recognizable stays

The 9 examples below hit every cell.

Worked examples

Worked example Example 1 — Cell C1 (bounded simulation, decidable)

Statement. $A_{D F A} = {⟨ B, w ⟩ : B is a DFA that accepts w}$ . Is it decidable?

Forecast: guess before reading — will the simulating machine ever be at risk of looping?

Steps.

Read $⟨ B, w ⟩$ and put a pointer at $B$ 's start state. Why this step? A DFA has a fixed finite set of states and reads exactly one symbol per move — there is no "go back and wait" instruction.
Feed the symbols of $w$ one by one, moving the pointer along $B$ 's transitions. This takes exactly $∣ w ∣$ moves ( $∣ w ∣$ = the number of symbols in $w$ ). Why this step? Because the move count is bounded by the input length, the simulation cannot loop — see the ceiling in the figure below.
After $∣ w ∣$ moves, accept iff the pointer sits on an accept state; else reject. Why this step? This is the definition of " $B$ accepts $w$ ".

Verify: every branch reaches step 3 in $\leq ∣ w ∣$ steps and then halts. No loop path exists, so members are accepted and non-members are rejected — a decider. Fits C1. ✔

Worked example Example 2 — Cell C2 (unbounded simulation, recognizable but undecidable)

Statement. $A_{T M} = {⟨ M, w ⟩ : M is a TM that accepts w}$ . Recognizable? Decidable?

Forecast: guess — where does the "loop" leak in that it couldn't in Example 1?

Steps.

Use a universal TM $U$ : it reads $⟨ M, w ⟩$ and simulates $M$ running on $w$ . Why this step? $U$ is literally a machine that runs other machines.
If the simulated $M$ accepts, $U$ accepts. If $M$ rejects, $U$ rejects. Why this step? Whenever $M$ halts, $U$ mirrors the verdict in finite time — so every member is accepted → recognizable.
Ask: is $U$ a decider? No — if $M$ loops on $w$ , then $U$ loops too. Why this step? $U$ has no way to detect an infinite run; the Halting Problem via Diagonalization proves no TM can decide $A_{T M}$ .

Verify: members ⇒ accept (finite), non-members ⇒ reject or loop. Exactly the recognizable-not-decidable profile of C2. ✔

Worked example Example 4 — Cell C4 (complement of a "loops-on-no" set is not recognizable)

Statement. Show $\overline{A_{T M}}$ (all $⟨ M, w ⟩$ with $M$ not accepting $w$ ) is not recognizable.

Forecast: you already know $A_{T M}$ is recognizable (Ex. 2). What does the iff-theorem force about its complement?

Steps.

Recall the crown-jewel theorem: $L$ is decidable $⟺$ both $L$ and $\overline{L}$ are recognizable. Why this step? It links complements to decidability directly.
Suppose, for contradiction, $\overline{A_{T M}}$ were recognizable. Then $A_{T M}$ (recognizable, Ex. 2) and $\overline{A_{T M}}$ are both recognizable. Why this step? We are setting up the theorem's left side.
By the theorem, $A_{T M}$ would be decidable — but Ex. 2 said it is undecidable. Contradiction. Why this step? A contradiction kills the supposition.

Verify: the only false assumption was " $\overline{A_{T M}}$ recognizable", so it is not recognizable. This is why the recognizable class is not closed under complement — fits C4. ✔

Worked example Example 5 — Cell C5 (both sides recognizable ⇒ decidable, dovetailing)

Statement. $M_{1}$ recognizes $L$ , $M_{2}$ recognizes $\overline{L}$ . Build a decider for $L$ .

Forecast: why is "run $M_{1}$ first, then $M_{2}$ " a trap here?

Steps.

On input $w$ , run $M_{1}$ and $M_{2}$ in lockstep: one step of $M_{1}$ , one step of $M_{2}$ , repeat. Why this step? This alternation is called dovetailing; it guarantees we never sit forever inside a machine that loops.
Since every $w$ is in exactly one of $L$ or $\overline{L}$ , exactly one of $M_{1}, M_{2}$ accepts $w$ in finite time. Why this step? Membership is total — $w$ can't be in neither.
If $M_{1}$ accepts → accept; if $M_{2}$ accepts → reject. Why this step? $M_{1}$ accepting means $w \in L$ ; $M_{2}$ accepting means $w \in \overline{L}$ .

Verify: one machine must accept, so the decider always halts. Contrast with the trap: running $M_{1}$ to completion could loop forever on a non-member and never reach $M_{2}$ . Fits C5. ✔

Worked example Example 7 — Cell C7 (the limiting input where the recognizer actually loops)

Statement. Give a concrete $⟨ M, w ⟩$ where the recognizer $U$ from Ex. 2 loops, showing recognizer $\neq =$ decider.

Forecast: guess what $M$ must do on $w$ to trap $U$ forever.

Steps.

Let $M$ be the one-state TM: "in state $q$ , on any symbol, move right and stay in $q$ ." Take $w = ε$ (empty string) — or any $w$ . Why this step? This $M$ never enters an accept or reject state; it slides right forever.
Feed $⟨ M, w ⟩$ to $U$ . $U$ simulates step 1, step 2, step 3, … Why this step? $U$ mirrors $M$ , and $M$ never halts.
$⟨ M, w ⟩ \in / A_{T M}$ (since $M$ does not accept), yet $U$ never rejects — it loops. Why this step? This is precisely the "no answer on a non-member" that separates recognizable from decidable.

Verify: a non-member on which the recognizer loops exists — so $U$ is genuinely not a decider. Fits the limiting cell C7. ✔

Worked example Example 8 — Cell C8 (real-world word problem)

Statement. A spam filter is given a fixed regex $R$ (say, matches emails containing "prize") and an email text $t$ of length $n = 30$ characters. "Is $t$ flagged?" is the language $L_{spam} = {⟨ R, t ⟩ : R matches t}$ . Decidable?

Forecast: which earlier cell does a regex matcher resemble?

Steps.

Convert $R$ to a DFA $B_{R}$ (regexes and DFAs recognize the same class — regular languages). Why this step? It reduces the problem to Example 1's setting.
Simulate $B_{R}$ on $t$ for exactly $n = 30$ steps. Why this step? Bounded by input length ⇒ no loop, just like C1.
Accept iff $B_{R}$ ends in an accept state. Why this step? That is what " $R$ matches $t$ " means.

Verify: halts in $30$ steps for members and non-members alike ⇒ decidable. Real filters do halt — this is why spam checking is a solvable problem, unlike $A_{T M}$ . Fits C8 (and reuses C1). ✔

Worked example Example 9 — Cell C9 (exam twist: "undecidable ⇒ not recognizable"?)

Statement. True or false: "If $L$ is undecidable, then $L$ is not recognizable."

Forecast: commit to True or False now, then read.

Steps.

Undecidable means "no total decider exists" — nothing more. Why this step? Pin down the exact meaning before reasoning.
But $A_{T M}$ (Ex. 2) is undecidable and recognizable. Why this step? One counterexample refutes a universal claim.
So "undecidable" and "not recognizable" are different conditions. Not-recognizable is strictly stronger (e.g. $\overline{A_{T M}}$ from Ex. 4). Why this step? It locates $A_{T M}$ between the two boundaries.

Verify: the statement is False; $A_{T M}$ is the witness. See Reductions and Rice's Theorem for a machine to generate more such languages. Fits C9. ✔

Recall Self-test: name the cell for each language

$A_{D F A}$ ::: C1 — decidable (bounded simulation) $A_{T M}$ ::: C2 — recognizable, undecidable $\overline{A_{T M}}$ ::: C4 — not recognizable $Σ^{*}$ and $\emptyset$ ::: C6 — trivially decidable " $M$ slides right forever" fed to $U$ ::: C7 — the loop that proves recognizer ≠ decider