Questions: Recursively Enumerable Languages: Semi-Decidability

Question 1

The Halting Problem H = {(M, w) | M halts on w} is recursively enumerable but not recursive. What does this imply about its complement H̄ = {(M, w) | M does not halt on w}?

• A. H̄ is also recursively enumerable, since we can simulate M and accept if it runs forever
• B. H̄ is recursive, since a machine can detect non-halting by running for a sufficiently long time
• C. H̄ is not recursively enumerable, because if H̄ were RE we could combine semi-deciders for H and H̄ to decide H, contradicting its undecidability
• D. H̄ is recursively enumerable but harder than H to semi-decide

Answer: (C)

If H̄ were RE, we would have a semi-decider for H̄ (halts and accepts iff M does NOT halt on w). Combined with the semi-decider for H (simulate M on w; accept if M halts), we could run both in parallel and decide H: whichever semi-decider accepts first gives the answer — and since every input is in exactly one of H and H̄, one must eventually accept. This would make H recursive, contradicting its undecidability. Therefore H̄ cannot be RE. More generally: if L is RE but not recursive, then L̄ is not RE.

Question 2

A Turing machine M accepts all strings in language L and loops forever on all strings not in L. What class does L belong to?

• A. Recursive (decidable), because M correctly identifies all members of L
• B. Not even recursively enumerable, because M provides no information about non-members
• C. Recursively enumerable (semi-decidable), because M halts and accepts exactly the strings in L, even though it may loop on non-members
• D. Context-sensitive, because the looping behavior corresponds to a bounded computation

Answer: (C)

The definition of a recursively enumerable (RE) language is exactly this: there exists a Turing machine that halts and accepts on every string in the language, and may loop forever on strings outside the language. M's behavior — accept on L, loop on L̄ — satisfies this definition precisely. The machine gives one-sided answers: 'yes' is confirmed by halting, but 'no' is never confirmed (just never answered). RE does not require the machine to halt on non-members, which is the key distinction from recursive (decidable) languages.

Question 3

A language L is recursive (decidable) if and only if both L and its complement L̄ are recursively enumerable.

• T. True
• F. False

Answer: True

This is the key closure theorem for RE languages. (→) If L is recursive, then both L and L̄ are RE: just use the decider for L directly as a semi-decider for L, and use the decider (which always halts) but accept on 'no' answers for L̄. (←) If both L and L̄ are RE, run their semi-deciders in parallel. Every input is in exactly one of L or L̄, so one semi-decider must eventually halt and accept — this gives a decider that always halts, making L recursive. The contrapositive is equally important: if L is RE but not recursive, then L̄ cannot be RE.

Question 4

Nearly every recursively enumerable language is also recursive, because any Turing machine that accepts a language can be modified to also reject non-members by detecting loops.

• T. True
• F. False

Answer: False

This is the fundamental misconception about RE languages. There is no general algorithm for detecting that a Turing machine will loop forever — this is precisely the content of the undecidability of the Halting Problem. A Turing machine that accepts L might loop forever on some inputs outside L, and no modification can guarantee it will halt on those inputs without potentially also changing which inputs it accepts. The Halting Problem is RE but not recursive precisely because we can verify 'yes' answers (simulate until halt) but cannot verify 'no' answers in general.

Question 5

Explain why the Halting Problem is recursively enumerable but not recursive, using the definitions of semi-decidability and decidability.

Model answer: The Halting Problem is RE because there exists a Turing machine that semi-decides it: given input (M, w), simulate M on w. If M halts, accept. This machine halts and correctly accepts every (M, w) pair where M halts on w. It never gives a wrong 'yes' answer. However, if M does not halt on w, the simulation runs forever — the machine loops rather than rejecting. This satisfies the RE definition (accept all yes-instances, may loop on no-instances) but not the recursive definition (which requires halting on all inputs with a correct yes/no answer). The Halting Problem is not recursive because no Turing machine can decide, for every (M, w), whether M halts on w — proven by diagonalization: any claimed decider D can be contradicted by constructing a machine that does the opposite of what D predicts.

The diagonalization proof constructs a machine D' that, on input M, runs D to predict whether M halts on M, then does the opposite. D' on input D': if D says D' halts, D' loops; if D says D' loops, D' halts. Either way D is wrong on this input. This shows no decider D can exist for the Halting Problem, while the simulation argument shows it is RE.