Questions: Recursively Enumerable and Co-RE Languages

Question 1

You build a Turing machine M that, given ⟨P, x⟩, simulates P on x and accepts if P halts — but loops forever if P does not halt. What can you conclude about the halting problem?

• A. M decides the halting problem, since it correctly identifies all halting instances
• B. M only recognizes the halting problem — it is a recognizer, not a decider, because it loops on non-halting instances rather than rejecting them
• C. M is impossible to build, since the halting problem is undecidable
• D. M proves the halting problem is in co-RE but not in RE

Answer: (B)

A recognizer only needs to accept all strings in the language — it makes no promise about non-members, which may cause it to loop. M is a valid recognizer: it accepts every ⟨P, x⟩ where P halts on x, so the halting problem is RE. But M is not a decider, because it loops forever on non-halting instances instead of halting with a 'reject.' A decider must halt on all inputs. The halting problem is RE-but-undecidable: we can recognize it (simulate and accept if halting) but cannot decide it (we cannot reliably detect non-halting). Undecidability and non-RE-membership are different things.

Question 2

A computer scientist has M₁ (recognizes language L, may loop on strings not in L) and M₂ (recognizes L̄, may loop on strings in L). She claims this is sufficient to decide L. Is she correct?

• A. No — a recognizer for L̄ only provides information about strings outside L and cannot help decide membership in L
• B. Yes — run M₁ and M₂ in parallel; one of them is guaranteed to eventually accept any input, giving the correct answer and always halting
• C. Only if both machines halt within polynomial time
• D. No — having recognizers for both L and L̄ is equivalent to having a single recognizer for L

Answer: (B)

Running M₁ and M₂ in dovetailed parallel creates a decider: for any input w, either w ∈ L (M₁ eventually accepts) or w ∉ L (M₂ eventually accepts). One must accept, so the combined machine always halts — it is a decider. This is the constructive proof of the theorem: L is decidable if and only if both L and its complement are RE. Note that we interleave steps of M₁ and M₂ rather than running M₁ to completion first (which might loop forever if w ∉ L).

Question 3

If language L is recursively enumerable, then its complement L̄ is also recursively enumerable.

• T. True
• F. False

Answer: False

RE is not closed under complementation — this is one of the most important facts in computability theory. The halting problem H is RE (a recognizer exists), but its complement co-H is not RE (no Turing machine can recognize co-H). If both H and co-H were RE, we could run recognizers for both in parallel to decide H — contradicting undecidability. Only the decidable languages sit at the intersection of RE and co-RE; languages that are RE-but-undecidable have complements that are co-RE-but-not-RE.

Question 4

A Turing machine that loops forever on inputs not in L — never halting with a reject — still qualifies as a recognizer for L.

• T. True
• F. False

Answer: True

Recognition only requires that the machine accepts every string in L — eventually, after any finite amount of computation. What the machine does on strings not in L is irrelevant to recognition: it may loop, or it may halt with a reject; both are acceptable behaviors for a recognizer. Only a decider must halt on all inputs (accepting members and explicitly rejecting non-members). Looping on negatives is the normal, expected behavior of a recognizer for an undecidable language — the machine simply has no way to determine that a non-member will never be accepted.

Question 5

Why is a language decidable if and only if it is both RE and co-RE? Explain using the definitions of recognition and decision.

Model answer: A language L is RE if a Turing machine M₁ accepts every string in L (possibly looping on strings not in L). L is co-RE if a Turing machine M₂ accepts every string not in L (i.e., M₂ recognizes the complement). If L is both RE and co-RE, run M₁ and M₂ in parallel on any input w: either w ∈ L (M₁ eventually accepts) or w ∉ L (M₂ eventually accepts). One must accept, so the combined machine always halts with the correct answer — it is a decider. Conversely, any decidable language is trivially both RE (the decider is itself a recognizer) and co-RE (run the decider and swap accept/reject to get a recognizer for the complement).

The 'if' direction (RE ∩ co-RE ⊆ decidable) is the constructive argument via parallel simulation. The 'only if' direction (decidable ⊆ RE ∩ co-RE) is immediate from definitions. Together they establish that decidability is exactly the property of being recognizable from both sides — the machine can certify both membership and non-membership. The halting problem fails precisely because its complement is not RE: we can certify halting instances but cannot certify non-halting ones.