1
$\begingroup$

I'm new to studying formal languages, so apologies if I get a lot of basic stuff wrong, but I'm trying to get an intuitive understanding of why the difference between two Recursively Enumerable languages (A and B, say) is not itself RE? I.e. why for A-B = Z, Z is not RE?

The basic set notation and maths I understand, but I've added a more textual description as I'm looking for an intuitive answer: let C = complement of B.

Some of the words C contains in its set would cause a TM for B to reject, others would cause it to never halt. So C is not RE.

Now, A-B = A n C, by basic set operations. The theory I've read now says that the intersection of an RE (A) and a non-RE (C) cannot be RE, which is why the original A-B = a non-RE. I accept this logic, but am struggling to understand intuitively how this is true, in terms of picturing a Turing Machine that halts or loops, given the input of words from A n C.

My First Attempt at an Intuitive Explanation:

My guess is that I've missunderstood something fundamental about TMs, and what their acceptance/rejection/looping on words of a language really means, but here we go:

Imagine a TM for the RE lang A. Every word in A will cause TM to accept. Now, isn't A-B just a subset of the words from the language A? Therefore, wouldn't all the words in A-B cause our TM to also accept? By this logic then, wouldn't the difference between two RE's, A-B, be an RE language, too?


My Final Thought:

I tried to picture this in different ways, with say having the condition be that you test your newly outputted language (A-B in this case), on a TM that accepts on each of the initial languages (A, B), and if the new language accepts on all those TMs, it must be RE? But that didn't hold for things like A u B.

So, I'm stuck as for an intuitive understanding as to why A - B is not RE, when A - B is just a subset of words of A, and A will accept on its TM? Further, what's the rule for how your new language (be it A-B, A u B, A* n B, etc) should accept in relation to TMs that accept on the initial languages?

Thanks very much for your help.

$\endgroup$
2
$\begingroup$

Given a language $L$, $L$ is RE if there is a TM $M$ such that $L(M) = L$. $L(M)$ is the set of words which $M$ accepts and it must be equal to $L$; words not in $L$ must cause $M$ either to reject or to never halt. It is not sufficient for $L$ to be a subset of $L(M)$, which is why your reasoning is incorrect.

Given RE languages $A$ and $B$, what makes $A \setminus B$ not RE (in general) is not the problem of knowing whether the input is in $A$; since $A$ is RE, there is a TM $M_A$ which you can simulate to find out (and if $M_A$ does not halt, the input is not in $A$ and, hence, not in $A \setminus B$ too; so there is no need to halt at all). The problem is that, to accept an input $w$ which is not in $B$, you need to simulate the respective TM $M_B$ on $w$ and accept if $M_B$ does not halt; hence, you need to solve an instance of the complement of the halting problem, which is (famously) not in RE.

$\endgroup$
  • $\begingroup$ Ok thanks very much, though I'm still confused on a couple of points. Let me pitch you these Q's, and then could you tell me if I'm right? 1) A\B will indeed be accepted by TM(A) as it is just a subset of A, but it's not the language of TM(A) because it's not the max possible set of words accepted by A? 2) The reason then that B\A is not RE is because whilst it is accepted by TM(A) it's not its language, and some of its words may cause TM(B) to reject or never halt? Hence, B-A is not the max poss set of words that will make a TM accept, so is not an RE lang. Is that all correct? Thanks! $\endgroup$ – TheRealPaulMcCartney Jan 8 at 14:41
  • 1
    $\begingroup$ @TheRealPaulMcCartney That seems correct, yes (though you seem to have written "$B \setminus A$" instead of "$A \setminus B$" in question number 2). I would not say $A \setminus B$ is "accepted" by $M_A$, though; it is only a subset of what $M_A$ accepts, nothing more than that. $\endgroup$ – dkaeae Jan 8 at 14:44
  • $\begingroup$ Ok, great, thanks! I did get B\A the wrong way, there. And I see what you're saying and agree with 2). However, now I'm confused as to how this model works with A n B... A n B is RE, yet A n B is also a subset of both A and B. And we just said a subset of a lang doesn't constitute a lang, as there are items missing from its set that would otherwise be accepted by TM(A) or TM(B)? $\endgroup$ – TheRealPaulMcCartney Jan 8 at 14:54
  • 1
    $\begingroup$ @TheRealPaulMcCartney For $A \cap B$ it works because you can simulate $M_A$ and $M_B$ simulatenously and accept if and only if both do. If either $M_A$ or $M_B$ does not accept a word $w$, then $w \not\in A \cap B$, so you need not halt. By the way, subsets of languages are still languages, of course! It is just that every TM accepts a unique language; (by definition) a TM does not "accept" subsets of its language. $\endgroup$ – dkaeae Jan 8 at 14:57
  • 1
    $\begingroup$ @TheRealPaulMcCartney Precisely. Glad to see you have learned something :) BTW if you believe the answer is a good one, then don't forget to mark it as an "accepted" answer (by clicking the tick box to the left). $\endgroup$ – dkaeae Jan 8 at 19:33

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.