P61 · Bridge theorem (constructive proof)

🔊 Narration

Walks through the theorem, the forward direction, the interleaved-simulation construction, and applications.

🔊 Listen

1 · Theorem statement

Bridge theorem (Sipser §4.2, Theorem 4.22)

A language L is decidable if and only if both L and its complement L̅ are Turing-recognizable.

Why it deserves the name "bridge"

Decidable lies inside Recognizable. The theorem says decidability = "doubly recognizable" — you need a recognizer for L AND one for ¬L. Either one alone isn't enough (A_TM has a recognizer but its complement doesn't, so A_TM is undecidable).

🔊 Listen

2 · Construction · build a decider from R_L and R_¬L

🔊 Listen

3 · The forward direction (⇒)

If L is decidable, both L and L̅ are recognizable

Easy. Let D be a decider for L. D always halts and outputs accept/reject. As a recognizer for L, D works directly. For L̅, build D′: on input x, run D(x), output the OPPOSITE answer. D′ is a decider for L̅, hence a recognizer.

🔊 Listen

4 · The reverse direction (⇐) — the constructive trick

Given recognizers R_L and R_¬L, build a decider for L

The new machine D on input x:

Simulate R_L on x AND R_¬L on x in parallel, by running them in lockstep (one step of R_L, then one step of R_¬L, then back).
If R_L accepts: D accepts.
If R_¬L accepts: D rejects.
Both can't accept (would mean x ∈ L AND x ∉ L). Exactly one accepts, eventually — because either x ∈ L (so R_L halts and accepts) or x ∉ L (so R_¬L halts and accepts).

Why D always halts: for every x, exactly one of x ∈ L or x ∉ L holds; the corresponding recognizer is guaranteed to halt and accept; the parallel simulation reaches that decision in finite time.

🔊 Listen

5 · Q&A defence notes

Q1. Why does "interleaved" matter? Couldn't we just run R_L first, then R_¬L?
No — R_L might loop forever on inputs not in L. If x ∉ L, running R_L first would never finish, and we'd never get to R_¬L. Interleaving guarantees that we make progress on both simulations.
Q2. Why can't both recognizers accept the same x?
R_L accepts x ⇒ x ∈ L. R_¬L accepts x ⇒ x ∉ L. Both accepting would mean x ∈ L AND x ∉ L, a contradiction. So at most one accepts.
Q3. Why must some recognizer eventually accept?
Every x is in L or in L̅ (law of excluded middle for language membership). The matching recognizer accepts strings in its language. Recognizers don't have to halt on rejections, but they do halt on accepts — so the right one will halt and accept on every x.
Q4. Application — give an example where the bridge theorem is the key step in proving undecidability.
A_TM is recognizable (Universal TM). If A_TM were decidable, then ¬A_TM would be recognizable too (by the forward direction). But ¬A_TM is known to be NOT recognizable. Contradiction. So A_TM is undecidable. The bridge theorem is the engine for this argument.
Q5. Application — EQ_TM is neither recognizable nor co-recognizable. What does that imply?
If EQ_TM were decidable, both it and ¬EQ_TM would be recognizable (forward direction). Since neither is, EQ_TM is "even worse than" A_TM: it's a strictly harder undecidable problem.