Exam Prep — Undecidability Triple

Exam Pattern

The exam always gives a language L over TM encodings. Three fixed sub-parts, same structure every time:

Part	Task	Pts	What you do
(a)	Prove L is TR or co-TR	2	Build a recognizer (for L or for L̄)
(b)	Prove L is undecidable	4	Mapping reduction from A_TM, E_TM, or EQ_TM
(c)	Prove L is not TR / not co-TR	1	Combine (a) + (b) via complement logic — free point

Every exam instance

24-25 endterm Q7: L = {⟨M⟩ | M is a DTM with an unreachable reject state}. (a) co-TR (2pts) (b) undecidable (4pts) (c) not TR (1pt)

24-25 resit Q7: L = {⟨M,k⟩ | M accepts at least k words of length ≥ k}. (a) TR (2pts) (b) undecidable (4pts) (c) not co-TR (1pt)

23-24 endterm Q9: L = {⟨M₁,M₂⟩ | {⟨M₁⟩,⟨M₂⟩} ∩ (L(M₁) ∪ L(M₂)) = ∅}. (a) co-TR (2pts) (b) undecidable (5pts) (c) not TR (1pt)

Decidability Reference Table

Problem	Definition	TR?	co-TR?	Decidable?
A_TM	{⟨M,w⟩ : M accepts w}	Yes	No	No
E_TM	{⟨M⟩ : L(M) = ∅}	No	Yes	No
EQ_TM	{⟨M₁,M₂⟩ : L(M₁) = L(M₂)}	No	No	No

Key theorem: L is decidable if and only if L is both TR and co-TR.

The Template

Part (a): Prove TR or co-TR — 2 pts

Decision tree: which side can you detect?

"Can you confirm membership?" → Build a recognizer for L → L is TR
"Can you confirm non-membership?" → Build a recognizer for L̄ → L is co-TR

If L is Turing-recognizable (TR): Build a TM that accepts when input is in L. May loop on non-members.

Dovetailing: enumerate all strings s₁, s₂, …, run M on each for i steps, accept if condition met
Direct simulation: run M on specific input(s), accept if condition observed

If L is co-Turing-recognizable (co-TR): Build a TM that accepts the COMPLEMENT L̄. Equivalently: build a TM that accepts when input is NOT in L.

Same dovetailing / simulation techniques, but aimed at detecting violations of L's condition

Rule of thumb: "finite/bounded properties" → often co-TR (check finitely many cases to refute). "Infinite/unbounded properties" → often TR (enumerate to confirm).

Part (b): Prove undecidable — 4 pts (THE CORE SKILL)

This is a mapping reduction. You prove: "if L were decidable, then A_TM would be decidable too — contradiction." Three steps:

Step 1 — Setup: Assume R decides L.

Step 2 — Build the reduction: Construct a decider S for A_TM:

S = "On input ⟨M, w⟩:
  1. Construct M' = "On input x:
       Run M on w.
       If M accepts → [behave so L(M') SATISFIES L's condition]
       If M rejects/loops → [behave so L(M') VIOLATES L's condition]"
  2. Run R on ⟨M'⟩ (or ⟨M', k⟩ etc.)
  3. Output R's answer (or flip it, if the mapping is inverted)."

Step 3 — Argue both directions:

YES → YES: M accepts w → L(M') = [something in L] → R accepts → S accepts
NO → NO: M doesn't accept w → L(M') = [something not in L] → R rejects → S rejects

Therefore S decides A_TM. Contradiction.

The most common M' construction

Almost always: M' ignores its own input x, runs M on w, then either accepts everything (Σ*) or nothing (∅). This swings L(M') between satisfying and violating L's condition.

M accepts w → L(M') = Σ*. M doesn't accept w → L(M') = ∅.

You never RUN M'. You just BUILD its description and hand it to R. M' is a specification, not an execution.

How to choose the source problem:

A_TM — default choice. Works for almost every exam problem. Input is ⟨M,w⟩.
E_TM — use when L is about emptiness/non-emptiness. Input is ⟨M⟩.
EQ_TM — rare. Only when L involves comparing two machines.

Part (c): Complement logic — 1 pt (FREE point)

The logic: TR + co-TR = decidable. So if one side holds and decidability fails, the other side must fail.

If (a) proved	And (b) proved undecidable	Then (c) concludes
L is co-TR	L is undecidable	L is not TR
L is TR	L is undecidable	L is not co-TR

Exam sentence: "From (a), L is [TR/co-TR]. From (b), L is undecidable. If L were also [co-TR/TR], then L would be decidable (TR + co-TR = decidable). Contradiction. Hence L is not [co-TR/TR]."

Worked Example — Resit 24-25 Q7

L = {⟨M,k⟩ | M is a TM that accepts at least k words of length ≥ k}

(a) Prove L is Turing-recognizable — 2 pts

Build a recognizer for L "On input ⟨M,k⟩: Let s 1, s 2, \dots be all strings in Σ* with |s i | \geq k Initialise counter = 0 For i = 1, 2, 3, \dots: Run M for i steps on each of s 1, \dots, s i If M accepts any s j (not previously counted), increment counter If counter \geq k, accept " This is a recognizer: if M really does accept \geq k long words, dovetailing will eventually find them. If not, we loop forever. That's fine — TR only requires halting on yes-instances.

(b) Prove L is undecidable — 4 pts

Step 1 — Setup Assume R decides L. We build a decider S for A TM . Step 2 — Construct the reduction S = "On input ⟨M, w⟩: Construct M' = "On input x: Run M on w. If it accepts, accept. If it rejects, reject." Run R on ⟨M', 1⟩. If R accepts, accept. Otherwise, reject." Step 3 — Argue both directions M accepts w \to L(M') = Σ* (accepts everything) \to M' accepts \geq 1 word of length \geq 1 \to ⟨M',1⟩ \in L \to R accepts \to S accepts ✓ M doesn't accept w \to L(M') = \emptyset \to ⟨M',1⟩ \notin L \to R rejects \to S rejects ✓ S decides A TM . But A TM is undecidable. Contradiction. ∎

(c) Prove L is not co-Turing-recognizable — 1 pt

From (a), L is TR. From (b), L is undecidable. If L were also co-TR, then L would be decidable (since TR + co-TR = decidable). But L is undecidable. Contradiction. Hence L is not co-TR. ∎

Worked Example — Endterm 24-25 Q7

L = {⟨M⟩ | M is a DTM with an unreachable reject state}

(a) Prove L is co-Turing-recognizable — 2 pts

Build a recognizer for L̄ (complement: "M has a REACHABLE reject state") "On input ⟨M⟩: Let s 1, s 2, \dots enumerate all strings in Σ* For i = 1, 2, 3, \dots: Run M on s 1, \dots, s i for i steps each If M reaches q reject on any s j, accept " If M has a reachable reject state, some input will reach it, and dovetailing finds it. If not, we loop. This recognizes L̄, so L is co-TR.

(b) Prove L is undecidable — 4 pts

Step 1 — Setup Assume R decides L. We build a decider S for A TM . Step 2 — Construct the reduction S = "On input ⟨M, w⟩: Construct M' = "On input x: Run M on w. If it accepts, accept. If it rejects, reject." Run R on ⟨M'⟩. If R accepts, accept. Otherwise, reject." Step 3 — Argue both directions M accepts w \to L(M') = Σ* \to M' never rejects \to q reject unreachable \to ⟨M'⟩ \in L \to R accepts \to S accepts ✓ M rejects w \to L(M') = \emptyset \to M' rejects every input \to q reject reachable \to ⟨M'⟩ \notin L \to R rejects \to S rejects ✓ S decides A TM . But A TM is undecidable. Contradiction. ∎

(c) Prove L is not TR — 1 pt

From (a), L is co-TR. From (b), L is undecidable. If L were also TR, then L would be decidable (since TR + co-TR = decidable). But L is undecidable. Contradiction. Hence L is not TR. ∎

Practice

Q1 — Endterm 23-24 Q9 (real exam, 8 pts)

L = {⟨M₁,M₂⟩ | {⟨M₁⟩, ⟨M₂⟩} ∩ (L(M₁) ∪ L(M₂)) = ∅}

(a) Prove L is co-TR (2 pts). (b) Prove L is undecidable (5 pts). (c) Prove L is not TR (1 pt).

Solution

(a) co-TR: Build a recognizer for L̄ (complement: {⟨M₁⟩, ⟨M₂⟩} ∩ (L(M₁) ∪ L(M₂)) ≠ ∅).

"On input ⟨M₁,M₂⟩: Dovetail — run M₁ and M₂ on both ⟨M₁⟩ and ⟨M₂⟩. If any machine accepts either encoding, accept."

Only 4 simulations to interleave. If the intersection is non-empty, at least one will halt and accept.

(b) Undecidable: Reduce from A_TM.

Step 1: Assume R decides L.

Step 2: Build decider S for A_TM:

S = "On input ⟨M, w⟩:

Construct M' = "On input x: Run M on w. If accepts, accept."
Let T_reject = a TM that rejects every input (L(T_reject) = ∅).
Run R on ⟨M', T_reject⟩.
If R accepts, reject. If R rejects, accept."

Step 3: Both directions:

M accepts w → L(M') = Σ* → ⟨M'⟩ ∈ L(M') → {⟨M'⟩, ⟨T_reject⟩} ∩ (L(M') ∪ L(T_reject)) ≠ ∅ → ⟨M', T_reject⟩ ∉ L → R rejects → S accepts ✓
M doesn't accept w → L(M') = ∅ → intersection = ∅ → ⟨M', T_reject⟩ ∈ L → R accepts → S rejects ✓

Note the flip: R's answer is inverted because A_TM membership maps to L non-membership here.

S decides A_TM. Contradiction. ∎

(c) Not TR: co-TR (from a) + undecidable (from b) → not TR. ∎

Q2 — Palindrome acceptance

L = {⟨M⟩ | M accepts at least one palindrome}

(a) Prove L is TR or co-TR. (b) Prove L is undecidable. (c) Prove L is not TR/co-TR.

Solution

(a) TR: Enumerate all palindromes p₁, p₂, … Dovetail: run M on p₁, …, p_i for i steps. If M accepts any palindrome, accept.

If M accepts a palindrome, dovetailing eventually finds it. If not, we loop forever. TR. ✓

(b) Undecidable: Reduce from A_TM.

Step 1: Assume R decides L.

Step 2: Build decider S for A_TM:

S = "On input ⟨M, w⟩:

Construct M' = "On input x: Run M on w. If accepts, accept."
Run R on ⟨M'⟩.
If R accepts, accept. Otherwise, reject."

Step 3: Both directions:

M accepts w → L(M') = Σ* ⊇ palindromes → ⟨M'⟩ ∈ L → R accepts → S accepts ✓
M doesn't accept w → L(M') = ∅ → no palindromes accepted → ⟨M'⟩ ∉ L → R rejects → S rejects ✓

S decides A_TM. Contradiction. ∎

(c) Not co-TR: TR (from a) + undecidable (from b) → not co-TR. ∎

Q3 — Accepts empty string

L = {⟨M⟩ | ε ∈ L(M)} (M accepts the empty string)

(a) Prove L is TR or co-TR. (b) Prove L is undecidable. (c) Prove L is not TR/co-TR.

Solution

(a) TR: Run M on ε. If it accepts, accept.

If M accepts ε, we halt and accept. If M loops on ε, we loop. TR. ✓

(b) Undecidable: Reduce from A_TM.

Step 1: Assume R decides L.

Step 2: Build decider S for A_TM:

S = "On input ⟨M, w⟩:

Construct M' = "On input x: Ignore x, run M on w. If accepts, accept."
Run R on ⟨M'⟩.
If R accepts, accept. Otherwise, reject."

Step 3: Both directions:

M accepts w → L(M') = Σ* → M' accepts ε → ⟨M'⟩ ∈ L → R accepts → S accepts ✓
M doesn't accept w → L(M') = ∅ → M' doesn't accept ε → ⟨M'⟩ ∉ L → R rejects → S rejects ✓

S decides A_TM. Contradiction. ∎

(c) Not co-TR: TR (from a) + undecidable (from b) → not co-TR. ∎