If you want to make money online : Register now

[Solved]: Symmetric Difference of Turing Recognizable and Finite Languages

, ,
Problem Detail:

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?

Answered By : babou

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44091

3.2K people like this