Decidability — decidable (recursive) and recognizable (recursively enumerable) languages: Visual walkthrough

Step 1 — The three fates of a machine

WHAT. Before any theorem, we must agree on what a machine can do when it reads a string. Picture a robot with a paper tape. You feed it a string $w$ (a finite line of symbols like 1011). The robot reads, scribbles, moves back and forth, and eventually its light does one of exactly three things.

WHY. Everything on this page — the whole "decidable vs recognizable" split — comes from the fact that there is a third fate. If robots only ever accepted or rejected, this topic would not exist. So we must see the third fate before we use it.

PICTURE. Three roads leave the robot.

Figure — Decidability — decidable (recursive) and recognizable (recursively enumerable) languages

🟩 Accept — green light, robot stops, means "YES, $w$ is in my set."
🟥 Reject — red light, robot stops, means "NO, $w$ is not in my set."
⚫ Loop — the robot never stops. No light ever. This is the villain of the story.

Step 2 — Draw the two classes as nested regions

WHAT. We name two collections of languages (a language is just a set of strings). Decidable = languages with an always-halting machine. Recognizable = languages with a green-on-members machine (loop allowed on non-members).

WHY. We must know where the target theorem lives before we prove it. The theorem is a bridge from the outer region to the inner region, so let us see the regions first.

PICTURE. Two circles, one inside the other.

The inner disk = decidable. The outer ring = recognizable.
Inner sits inside outer because a decider is already a recognizer: it lights green on members and (bonus) red instead of looping on non-members. Doing more than required still counts.
The star $A_{T M}$ (the acceptance problem) sits in the ring only — recognizable but not decidable — proof that the two circles are genuinely different, not the same circle drawn twice.

$always halts Decidable ⊊ green on members, may loop Recognizable$

Read the symbols: $⊊$ means "is inside, but not equal to" — the inner circle is strictly smaller.

Step 3 — The easy half: decidable ⇒ both directions recognizable

WHAT. We prove the " $\Rightarrow$ " arrow. Assume $L$ is decidable. We must show both $L$ and its complement $\overline{L}$ are recognizable.

WHY. The theorem is an "if and only if" ( $⟺$ ), which is really two claims glued together. The forward claim is the gentle one, so we clear it first and see the flip trick that we will fail to reuse later — that failure is the whole plot.

PICTURE. One decider, and its mirror twin.

Let $M$ be the always-halting machine for $L$ . Build a twin $M^{'}$ that runs $M$ and then swaps the lights:

$M^{'} : run M ⟶ {M accepts \Rightarrow M^{'} rejects M rejects \Rightarrow M^{'} accepts$

$M$ = original decider for $L$ ; because it always halts, its light is always one of green/red — never black.
The swap only makes sense because there is always a light to swap. This is the fragile hinge.

Result: $M^{'}$ decides $\overline{L}$ , so $\overline{L}$ is decidable, hence recognizable. And $L$ itself is recognizable (Step 2). ✔ Forward direction done.

Step 4 — The hard half: set up two half-machines

WHAT. Now the " $\Leftarrow$ " arrow. Assume we are given two recognizers: $M_{1}$ that lights green exactly on $L$ , and $M_{2}$ that lights green exactly on $\overline{L}$ . Goal: build a single machine $D$ that always halts and decides $L$ .

WHY. This is the surprising claim — two loop-prone half-answerers combining into one always-answering machine. We first stage the pieces so the mechanism (next step) is visible.

PICTURE. Two boxes and the one fact that saves us.

$M_{1}$ = recognizer for $L$ : green on members of $L$ , may loop otherwise.
$M_{2}$ = recognizer for $\overline{L}$ : green on members of $\overline{L}$ , may loop otherwise.

The magic fact printed in the middle: $every string w is in L or \overline{L}, never both, never neither.$

$L \cup \overline{L} = Σ^{*}$ (everything) and $L \cap \overline{L} = \emptyset$ (no overlap).
Consequence: exactly one of $M_{1}$ , $M_{2}$ is destined to light green on this $w$ — and it does so after finitely many steps.

So somewhere out there a green light is waiting for us. The only danger is that the other machine loops and blocks our view.

Step 5 — Dovetailing: run both machines at once

WHAT. We build $D$ by running $M_{1}$ and $M_{2}$ in parallel, one step each, alternating forever until one lights green. This alternating simulation is called dovetailing.

WHY THIS TOOL. Why not just "run $M_{1}$ to the end, then $M_{2}$ "? Because if $w \in \overline{L}$ , then $M_{1}$ may loop forever and you'd never reach $M_{2}$ . You'd be stuck watching a black-road machine, when a green light was waiting next door. Dovetailing answers the exact question "how do I wait on two machines when one might never stop?" — by never fully committing to either.

PICTURE. A zig-zag clock ticking between the two machines.

Ticks go: $M_{1}$ step 1, $M_{2}$ step 1, $M_{1}$ step 2, $M_{2}$ step 2, …

$D (w) : for t = 1, 2, 3, \dots {advance M_{1} one step; if green \Rightarrow D accepts advance M_{2} one step; if green \Rightarrow D rejects$

$t$ = the tick counter; each tick nudges both machines forward once.
$M_{1}$ green $\Rightarrow$ $w \in L$ $\Rightarrow$ $D$ says accept (a real, final YES).
$M_{2}$ green $\Rightarrow$ $w \in \overline{L}$ $\Rightarrow$ $D$ says reject (a real, final NO).

Why $D$ always halts: by Step 4, one of the two green lights is guaranteed to arrive at some finite tick $t^{⋆}$ . The looping of the other machine can no longer trap us, because we only ever run it one step at a time — it never gets to hog the clock. So $D$ reaches a light and stops. $D$ decides $L$ . ∎

Step 6 — The degenerate case that makes the theorem sharp

WHAT. We check what happens when the hypothesis is only half satisfied: $L$ recognizable but $\overline{L}$ not recognizable. The theorem then forbids $L$ from being decidable. We watch the machinery break exactly where it should.

WHY. A theorem is only trustworthy if we test its edges. Here the edge is $A_{TM}$: it is recognizable (universal simulation lights green when $M$ accepts $w$ ), but its complement is not recognizable.

PICTURE. The dovetailing engine with one fuel line cut.

$M_{1} = U$ , the universal machine, recognizes $A_{T M}$ : green when $M$ accepts $w$ . Fine.
But there is no $M_{2}$ recognizing $\overline{A_{T M}}$ — diagonalization proves none can exist.
With no $M_{2}$ , the right half of the dovetail is empty. On a non-member $w$ , $M_{1}$ loops and nothing else can ever light green. $D$ cannot be built. $A_{T M}$ stays undecidable.

$A_{T M} \in RE, \overline{A_{T M}} \in / RE \Rightarrow A_{T M} \in / Decidable .$

This is exactly Step 3's fragile hinge biting back: no halt, no light, no swap, no decider. The two halves of the $⟺$ fit together with no gap — this is why the theorem is stated as an equivalence and not a one-way implication.

Step 7 — Reassembling the biconditional

WHAT. Glue Steps 3 and 5 into the final statement.

WHY. An $⟺$ is proven only when both arrows are in hand. Let us name them and confirm no case is missing.

PICTURE. The two arrows closing the loop.

$\Rightarrow$ (Step 3): decidable $\Rightarrow$ $L$ recognizable and $\overline{L}$ recognizable.
$\Leftarrow$ (Step 5): $L$ recognizable and $\overline{L}$ recognizable $\Rightarrow$ decidable (dovetail).
Edge case (Step 6): drop either hypothesis $\Rightarrow$ the conclusion can fail. So neither half is redundant.

$L decidable ⟺ L \in RE and \overline{L} \in RE$

Every case is covered: both recognizable (decidable), one recognizable (not decidable, Step 6), neither recognizable (certainly not decidable). No scenario is left unshown.

The one-picture summary

One diagram compresses the whole walkthrough: two recognizers feed a dovetailing clock; whichever half lights green first hands the always-halting decider its final answer — and the moment one half has no partner, the bridge collapses and we fall back into the undecidable outer region.

Recall Feynman retelling — explain the whole walkthrough to a 12-year-old

Imagine a locked door and two friends. Friend A shouts "YES it's locked!" the instant she's sure it's locked — but if it's unlocked she just stares at it forever, silent. Friend B is the opposite: he shouts "YES it's unlocked!" the instant he's sure, but stays silent forever if it's locked. Each friend alone is useless for the "no" case — you'd wait forever. But here's the trick: make them take turns, one glance each, back and forth, back and forth. Since the door is definitely either locked or unlocked, one friend is guaranteed to shout eventually. Whoever shouts first tells you the real answer, and you stop. Two half-answerers became one full answerer — that's a decider. Now the catch (Step 6): this only works if both friends exist. For some doors ( $A_{T M}$ ) Friend A exists but Friend B is impossible to hire — so you can hear "locked!" but never a reliable "unlocked!", and no full answerer can ever be built. That single missing friend is why "recognizable" is strictly weaker than "decidable," and why RE is not closed under complement. See also Reductions and Rice's Theorem and Chomsky Hierarchy.

Recall Self-test

Why must the two recognizers be run in parallel, not one-then-the-other? ::: Because the first one may loop forever on this input, blocking you from ever reaching the second; alternating steps guarantees the green-lighting machine is reached in finite time. If $L \in$ RE but $\overline{L} \in /$ RE, is $L$ decidable? ::: No — by the theorem, decidability needs both $L$ and $\overline{L}$ in RE. Why does the accept/reject swap trick fail for recognizers? ::: A recognizer may loop on non-members, so there is no halted light to swap.