Suppose language L is Turing-recognizable and its complement L̄ is also Turing-recognizable. What can you conclude?
AL is in RE but may or may not be decidable — more information is needed
BL is decidable, because you can run both recognizers in parallel and always get an answer
CL̄ is decidable, but L itself might not be
DNothing — recognizability of both L and L̄ has no implications for decidability
This is the key theorem: L is decidable if and only if both L and L̄ are Turing-recognizable. The proof is constructive: run the recognizer for L and the recognizer for L̄ in parallel on any input. Since every input is either in L or in L̄, one of the two recognizers must eventually accept. Whichever accepts first gives you a definitive yes-or-no answer — and crucially, this parallel simulation always halts. You never loop forever.
Question 2 Multiple Choice
A Turing machine M is given as input along with a string w. You simulate M on w and the simulation runs for 10,000 steps without halting. What can you correctly conclude about HALT_TM?
AM does not halt on w — this is evidence that the complement of HALT_TM is recognizable
BYou cannot conclude that M will never halt — the recognizer for HALT_TM can loop forever on non-halting inputs, which is why HALT_TM is not decidable
CM eventually halts — 10,000 steps is enough to confirm this
DHALT_TM is co-RE because you can detect non-halting after a finite number of steps
This is the core asymmetry of HALT_TM. You can recognize it: if M halts, your simulation eventually terminates and you output 'yes.' But if M loops forever, your simulation loops forever too — you can never output 'no.' No matter how many steps you observe without halting, you cannot rule out that M halts on step 10,001. This is exactly why HALT_TM's complement is not recognizable: confirming that a TM loops forever would require running it forever, which is not a finite computation.
Question 3 True / False
Every decidable language is Turing-recognizable.
TTrue
FFalse
Answer: True
This follows immediately from definitions. A decider always halts and correctly accepts strings in L and rejects strings not in L. This is strictly stronger than recognition, which only requires accepting strings in L (and allows looping on strings not in L). So any decider is also a recognizer — recognition is a weaker condition. The class of decidable languages is a proper subset of the Turing-recognizable (RE) languages.
Question 4 True / False
If a language L is Turing-recognizable, then L is expected to be decidable — it just might take a very long time to compute the answer.
TTrue
FFalse
Answer: False
This is the most common misconception in this area. Recognizability does not mean 'slow decidability' — these are categorically different. A recognizer for L can loop forever on inputs not in L; it never produces a 'no' answer for those inputs at all. A decider must halt on every input, including non-members. HALT_TM is the canonical counterexample: it is Turing-recognizable (simulate and wait for halting) but not decidable (there is no algorithm that always halts and correctly answers whether an arbitrary TM halts).
Question 5 Short Answer
Explain why the halting language HALT_TM being in RE but not in co-RE proves it is undecidable.
Think about your answer, then reveal below.
Model answer: A language is decidable if and only if it is in both RE and co-RE. HALT_TM is in RE because you can recognize it: simulate the TM and accept if it halts. But HALT_TM's complement — the set of (M, w) pairs where M does not halt on w — is not recognizable. No Turing machine can confirm that a TM loops forever in finite time. Since HALT_TM is not in co-RE, it is not in the intersection RE ∩ co-RE, and that intersection is exactly the decidable languages. Therefore HALT_TM is undecidable.
The key is that decidability requires being in both RE and co-RE simultaneously. If L is decidable, you can trivially recognize both L and its complement (just run the decider and flip the answer). Conversely, if both L and L̄ are recognizable, run them in parallel to decide. HALT_TM fails because its complement is not recognizable — there's an asymmetry between 'yes' instances (the TM halts, your simulator confirms it) and 'no' instances (the TM loops, your simulator loops with it). That asymmetry is why HALT_TM sits outside the decidable languages.