2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Andreas correctly explains why "closed under union" happens to be harder to prove for the class of recursively enumberable languages than for the class of recursive ones. But I don't think is is necessarily the case that all sorts of closure properties are easier to prove for one class than for the others. The r.e. languages is a larger class, so the assumptions you have tell you less there, but on the other hand what you need to establish is also less. It may all even out, or for other closure properties even be easier to show them for r.e. languages. $\endgroup$ – Henning Makholm Mar 17 '13 at 21:57
4
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thanks for the reply. But Turing Decidable guarantees that it will eventually come to a halt, even if it runs for an extremely long time. With Turing Recognizable, if it checks if a string is in A and doesn't find it for 1000 years, it still may come up a second after it 'gives up' and goes to Turing Machine B, so its not really tricky, it is just doing what it is supposed to do, which is run for as long as it needs to. Its hard for me to explain what I mean, but I still don't get why proving a Recognizable language is closed under some operation is 'tricky' when compared to the contrary... $\endgroup$ – AnchovyLegend Mar 17 '13 at 21:52
  • $\begingroup$ If A runs forever, then it hasn't found the string it was looking for yet, but it still might, sometime in the future, right? <---- This thought is what is confusing me. $\endgroup$ – AnchovyLegend Mar 17 '13 at 21:56
  • 2
    $\begingroup$ @Epsilon: It is true that the r.e. languages are closed under union -- the point is just that you need a more sophisticated argument than "first check one, then check the other" to show it. I can't see from your comment whether you actually have a sufficiently sophisticated argument in mind or you don't but have confused yourself into thinking you do. Expressing your reasoning clearly enough make that clear is why the problem is trickier. $\endgroup$ – Henning Makholm Mar 17 '13 at 22:00
  • $\begingroup$ I see what you mean by me not being to easily explain what it means proves that it is tricky... $\endgroup$ – AnchovyLegend Mar 17 '13 at 22:35
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.