Exam Prep — Fill-in Reduction

Exam Pattern

A partial mapping reduction is shown. The reduction function F is mostly written — you fill in what the constructed machine M' must do (what L(M') should be), and/or explain what the reduction proves about L.

Two sub-parts:

(a) "What should L(M') be?" — 1 pt. Read off from the reduction argument: figure out what L(M') needs to equal so the iff holds in both directions.
(b) "What does this reduction prove?" — 1–2 pts. State the conclusion: L is decidable / undecidable / not TR / not co-TR. Use the direction rules below.

Every exam instance

24-25 endterm Q8: Reduction from EQ_TM to L = {⟨M₁,M₂,M₃,M₄⟩ | ∀w ∈ Σ*: w is in exactly 1 or exactly 3 of these TMs' languages}. Fill in L(M₃) and L(M₄). Then: what does this prove about L?

24-25 resit Q8: Reduction from E_TM to L = {⟨M₁,M₂,c⟩ | M₁, M₂ have finite languages with |L(M₁)| − |L(M₂)| ≥ c}. Fill in L(M'). Output is ⟨M', M, 3⟩.

23-24 endterm Q11: Reduction from L to E_CFG. F converts grammar G to CNF, adds a new symbol. What is L? Does this prove L decidable?

The Mechanic

Backwards reasoning — how to find L(M')

Step 1. READ the reduction structure
   - What is the SOURCE problem? (A_TM, E_TM, EQ_TM, ...)
   - What is the TARGET problem? (the language L being analyzed)
   - What does F construct? (M', or a tuple like ⟨M', M, 3⟩)

Step 2. WORK BACKWARDS from the iff requirement
   For the reduction to be valid, both directions must hold:
   - YES case: if source input IS in the source language,
     what must L(M') be so that the output IS in L?
   - NO case: if source input is NOT in the source language,
     what must L(M') be so that the output is NOT in L?

Step 3. VERIFY both directions
   Does your choice of L(M') make YES → in L and NO → not in L?

Reduction direction rules — what A ≤_m B transfers

Upward (from source to target):
  A undecidable  →  B undecidable
  A not TR       →  B not TR
  A not co-TR    →  B not co-TR

Downward (from target to source):
  B decidable    →  A decidable
  B recognizable →  A recognizable

Complement trick:
  A ≤_m B  ⇔  Ā ≤_m B̄   (same reduction function works)

Common source problems and what they transfer:

Source	Known properties	What it proves about target
A_TM	Undecidable, TR, not co-TR	Target undecidable. Via complement: target not co-TR.
E_TM	Undecidable, co-TR, not TR	Target undecidable. Via complement: target not TR.
EQ_TM	Undecidable, not TR, not co-TR	Target undecidable, not TR, not co-TR.
E_CFG	Decidable	If reducing TO E_CFG: source is decidable.

Why the complement trick matters for A_TM and E_TM: A_TM is TR (not "not TR"), so A_TM ≤_m L doesn't directly prove L is not TR. But it does give Ā_TM ≤_m L̄, and Ā_TM is not TR → L̄ not TR → L not co-TR. Same logic applies to E_TM in the other direction.

Worked Example — Resit 24-25 Q8

L = {⟨M₁, M₂, c⟩ | M₁ and M₂ are TMs with finite languages such that |L(M₁)| − |L(M₂)| ≥ c}

Reduction from E_TM to L:

F = "On input ⟨M⟩: Construct M' = "On input w: (a) \dots Write ⟨M', M, 3⟩ to the output tape." What should L(M') be?

Step 1 — Read the structure

Source = E_TM. Target = L. Output tuple = ⟨M', M, 3⟩, so M₁=M', M₂=M, c=3.

Step 2 — Work backwards

YES case (M ∈ E_TM, i.e. L(M) = ∅):

Need ⟨M', M, 3⟩ ∈ L
So |L(M')| − |L(M)| ≥ 3
Since L(M) = ∅, |L(M)| = 0 → need |L(M')| ≥ 3
Both must have finite languages

NO case (M ∉ E_TM, i.e. L(M) ≠ ∅):

Need ⟨M', M, 3⟩ ∉ L
If L(M) is infinite → the "finite languages" condition fails → tuple is not in L regardless. Good.
If L(M) is finite but nonempty, |L(M)| ≥ 1 → need |L(M')| − |L(M)| < 3
If |L(M')| = 3 and |L(M)| ≥ 1, then 3 − |L(M)| ≤ 2 < 3 → not in L. Good.

Step 3 — Verify

Simplest answer: L(M') = {a, aa, aaa} — a fixed finite language of size 3.

L(M) = ∅ → |L(M')| − |L(M)| = 3 − 0 = 3 ≥ 3 → in L ✓
L(M) ≠ ∅, infinite → "finite languages" condition fails → not in L ✓
L(M) ≠ ∅, finite with |L(M)| ≥ 1 → 3 − |L(M)| ≤ 2 < 3 → not in L ✓

L(M') = {a, aa, aaa} — any fixed finite language of size exactly 3.

Worked Example — Endterm 24-25 Q8

L = {⟨M₁, M₂, M₃, M₄⟩ | ∀w ∈ Σ*: w is in the language of exactly 1 or exactly 3 of these TMs}

Reduction from EQ_TM to L:

F = "On input ⟨M 1, M 2 ⟩: Construct M 3 = "On input w: (a) \dots Construct M 4 = "On input w: (a) \dots Write ⟨M 1, M 2, M 3, M 4 ⟩ to the output tape."

(a) What should L(M₃) and L(M₄) be?

YES case (⟨M₁,M₂⟩ ∈ EQ_TM, i.e. L(M₁) = L(M₂)):

Need every w to be in exactly 1 or exactly 3 of {L(M₁), L(M₂), L(M₃), L(M₄)}
Since L(M₁) = L(M₂), every w is in both or neither of the first two
If w ∈ L(M₁) = L(M₂): already in 2 → need exactly 1 of {M₃, M₄} → total = 3 ✓
If w ∉ L(M₁) = L(M₂): in 0 → need exactly 1 of {M₃, M₄} → total = 1 ✓
So we need: for ALL w, w is in exactly one of L(M₃), L(M₄) — they partition Σ*

NO case (⟨M₁,M₂⟩ ∉ EQ_TM, i.e. L(M₁) ≠ L(M₂)):

Need some w NOT in exactly 1 or 3
Take w where w ∈ L(M₁) but w ∉ L(M₂) (exists since they differ)
w is in 1 of the first two
If L(M₃) = Σ* and L(M₄) = ∅: w ∈ L(M₃), w ∉ L(M₄) → total = 1 + 1 + 0 = 2
2 is not 1 or 3 → not in L ✓

L(M₃) = Σ*, L(M₄) = ∅ (or vice versa)

(b) What does this reduction prove about L?

EQ_TM ≤_m L. Since EQ_TM is undecidable, not TR, and not co-TR:

EQ_TM undecidable → L is undecidable
EQ_TM not TR → L is not TR
EQ_TM not co-TR → L is not co-TR

L is undecidable, not Turing-recognizable, and not co-Turing-recognizable.

Worked Example — Endterm 23-24 Q11

Reduction from L to E_CFG:

F = "On input ⟨G⟩: Convert G to CNF: G' = (V', Σ', R', S') Take symbol x \notin Σ', construct G'' = (V', Σ' \cup {x}, R' \cup {S' \to x}, S') Write ⟨G''⟩."

(a) Describe language L.

Key observation: G'' always has x ∈ L(G'') via the added rule S' → x. So L(G'') ≠ ∅ for any input G. Therefore ⟨G''⟩ ∉ E_CFG always.

The reduction maps everything to NO-instances of E_CFG. For A ≤_m B: yes-instances of A must map to yes-instances of B. Since nothing maps to yes, L (the source) must have no yes-instances.

L = ∅

(b) Does this prove L decidable?

Yes. ∅ is decidable (reject everything). And E_CFG is decidable. The reduction confirms: L ≤_m E_CFG, E_CFG decidable → L decidable.

Yes — L is decidable (it's the empty language).

Practice

Q1 — A_TM to "accepts everything"

Reduction from A_TM to L. F = "On input ⟨M,w⟩: Construct M' = 'On input x: Run M on w. If accepts, accept.' Write ⟨M'⟩."

L = {⟨M⟩ | L(M) = Σ*}.

(a) Verify L(M') works for both cases. (b) What does A_TM ≤_m L prove?

Solution

(a) Verify:

M accepts w → M' accepts every x → L(M') = Σ* → ⟨M'⟩ ∈ L ✓
M doesn't accept w → M' loops/rejects on every x → L(M') = ∅ → ⟨M'⟩ ∉ L ✓

(b) What it proves:

A_TM undecidable → L is undecidable
Complement trick: A_TM ≤_m L ⇔ Ā_TM ≤_m L̄. Ā_TM is not TR → L̄ is not TR → L is not co-TR.

Note: A_TM is TR, but TR transfers downward (B recognizable → A recognizable), so we can't conclude L is TR from this reduction. We use the complement trick instead to get the not-co-TR result.

L is undecidable and not co-Turing-recognizable.

Q2 — A_TM to "accepts at least 3 strings"

Given partial reduction from A_TM to L = {⟨M⟩ | M accepts at least 3 strings}.

F = "On input ⟨M,w⟩: Construct M' = 'On input x: [???]'. Write ⟨M'⟩."

What should M' do?

Solution

M' = "On input x: Run M on w. If accepts, accept."

M accepts w → L(M') = Σ* (infinite, ≥ 3) ✓
M doesn't accept w → L(M') = ∅ (0 < 3) ✓

M' ignores its input and runs M on w. If M accepts, M' accepts.

Q3 — Reduction TO a decidable language

The reduction goes FROM L TO A_DFA. What can we conclude about L?

Solution

A_DFA is decidable. L ≤_m A_DFA with A_DFA decidable → L is decidable.

Decidability transfers downward: if the target is decidable, the source must be too.

L is decidable.

Step 1 — Read the structure

Step 2 — Work backwards

Step 3 — Verify

(a) What should L(M3) and L(M4) be?

(b) What does this reduction prove about L?

(a) Describe language L.

(b) Does this prove L decidable?

(a) What should L(M₃) and L(M₄) be?