3
$\begingroup$

Let A be a Turing Recognizable Language and B a finite Language. I want to prove that their symmetric difference is Turing Recognizable.

My reasoning: B is finite, therefore the finite number of strings can be put through a DTM , M, such that L(M)= A. If M accepts, then remove that string from B and put it in a list, R. * Otherwise, leave it in B. The DTM for the symmetric difference just checks if it is either in B, which it accepts, R which it rejects or if M accepts.

I feel like I have simplified this somewhere, but I would appreciate any pointer in the right direction.

I am unsure how to determine the strings in both A and B. The way I have done it (above) would run forever, because if it is not in A and is in B, it would never halt. This would result in never getting past the * above.

How can it be determined if a string is in A and B?

$\endgroup$
  • $\begingroup$ Thank you! I appreciate the direction towards proper etiquette. $\endgroup$ – csonq Jul 1 '15 at 20:00
  • $\begingroup$ It's easy to determine if a string is in A and B but your question asks about the symmetric difference of A and B, which is something else entirely. $\endgroup$ – David Richerby Jul 1 '15 at 21:21
  • $\begingroup$ @D.W. The post does include questions. And the proof is presented as incomplete, and asking for help. $\endgroup$ – babou Jul 1 '15 at 23:21
  • $\begingroup$ How i was approaching it was to make a list of those string in both of them, it will be finite, reject them. If it is the rest of B accept. and then run it on A. So if I knew how to find A and B, then I can solve the rest, or so I think. $\endgroup$ – csonq Jul 1 '15 at 23:35
  • $\begingroup$ @babou, the questions were added after I wrote my earlier comment, and the request for help was made more specific. Thanks for letting me know that my earlier comment is now obsolete; I've deleted it. $\endgroup$ – D.W. Jul 2 '15 at 0:04
4
$\begingroup$

The symmetric difference $A\ominus B$ of a Turing Recognizable Language $A$ and a finite language $B$ is Turing Recognizable (i.e. recursively enumerable, or RE).

What you must do is prove that there is a Turing machine that recognizes $A\ominus B$, but you do not have to actually construct the machine. And that is very fortunate because, in general, you cannot.
[More precisely you can build that machine, but you will have in general no way to know it is the right one, as explained below.]

This is a sketch of the proof, which you should know how to complete.

First you prove that the union of a RE set $C$ and a finite set $D$ is a RE set $C\cup D$ (i.e. a Turing recongnizable set). That is pretty easy.

Then you prove that subtracting a finite set $D$ from a RE set $C$ produces a RE set $C\setminus D$. That is easily done by modifying the Turing machine that recognizes the RE set.

You simply modify the Turing machine recognizing $C$ so that it loops or reject when the input is an element of $D$

Now consider the finite set $B$. It can be split into two parts:

  • $B_1=B\setminus A$ containg all elements of $B$ that are not in $A$,

  • $B_2=B\cap A$, the intersection of $A$ and $B$.

Since $B$ is finite, both $B_1$ and $B_2$ are finite too.

It is easy to show that the symmetric difference is

$A\ominus B= (A\setminus B_2)\cup B_1$

Since we have shown that RE sets are closed under union with a finite set, and under subtraction of a finite set, the set $A\ominus B$ is also RE, i.e. Turing recognizable.

Thus there is a Turing machine that recognizes $A\ominus B$, but this proof does not tell you which. The reason is that there is no general way to determine what part of $B$ is the set $B_2$.

Actually you could construct $2^{|B|}$ Turing machines, each corresponding to one possibility for the set $B_2$ as subset of $B$. One of these Turing machines is the one you want. But there is no general procedure to determine which.

This kind of proof is called non constructive, because you can prove that an answer exists (i.e. the recognizer for the symmetric difference), but you cannot actually tell what it is.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ It's "subtraction", not "substraction". $\endgroup$ – Rick Decker Jul 2 '15 at 15:02
  • $\begingroup$ @RickDecker Thanks. No one ever corrected me, and I guess I never noticed. It is apparently a very common error (according to my web search). $\endgroup$ – babou Jul 2 '15 at 15:20

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.