Symmetric Difference of Turing Recognizable and Finite Languages
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.