Why is showing a language is Turing recognizable trickier than showing Turing decidable?

Question

I have written a proof to show that a Turing Decidable languages are closed under union (amongst other things). Later, I have written a proof to show that Turing Recognizable languages are closed under union.

I am supposed to identify why closing a Turing Recognizable language under some operation is trickier to prove than when dealing with Turing Decidable languages. However, the proofs are extremely similar and I am not sure what makes the proofs trickier other than the obvious, that Turing Recognizable may never halt.

I appreciate any suggestions on identifying what it is that make proving Turing Recognizable languages are closed under some operation is trickier than when dealing with Turing Decidable.

Answer 1

To decide whether a string is in the union of two recursive (= Turing decidable) languages $A$ and $B$, you (or an algorithm) can first check whether it's in $A$ and then, if necessary, check whether it's in $B$. In the case of recursively enumerable (= Turing recognizable) languages, that won't work, because, if your string isn't in $A$, then the "check whether it's in $A$" part will run forever and you'll never get around to checking whether it's in $B$.

Answer 2

Here's an example of an operation that it's definitely easier to prove the recursively enumerable languages closed under:

Input: A formal language $A\subseteq \Sigma^*$ for some alphabet $\Sigma$.

Output: The formal language $A' = \bigcup_{n\in\mathbb N}\;\{ w\in\Sigma^* \mid \mathtt{0}^nw \in A \}$.

This is slightly tricky to prove the r.e. languages closed under, but it is still much easier than for decidable languages, because the decidable languages are not closed under this operation at all. To wit, the result of applying it to the decidable language

$$ B=\{ \mathtt{0}^n\mathtt{1}\mathtt{0}^m\mathtt{1}w \mid \text{Turing machine $T_m$ halts in $n$ steps on input }w \}$$ is not a decidable language.