last day (16 days later) » 

11:51
Hello @dtldarek
I have a question
12:37
Hi, what's up?
13:08
@dtldarek Fine, thanks and you?
@dtldarek I have a question about the following:

If $A,B$ are recursively enumerable, then deduce if the sets $A \setminus B$, $A \triangle B=(A \cup B) \setminus{(A \cap B)}, AB, A \cap B$ are also recursive.
@dtldarek I have thought the following for $A \setminus{B}$. Since $A$ and $B$ are recursively enumerable then there is a Turing machine $M_1$ that computes $A$ and a Turing machine $M_2$ that computes $B$. Then we get the following Turing machine that computes $A \setminus{B}$.
@dtldarek Is my idea right?
13:32
M_2 instead of replying "no" can loop forever instead, but some of the later cases should be "yes" so that is not recursively-enumerable.
13:47
So we know that the machine will halt if the output is yes, otherwise the output is either no or the machine does not halt? @dtldarek
We should have that, but we don't
a language is RE if there is machine T that answers "yes" in finite time (whatever long) or answers "no" or loops forever (but only if it should have said no)
in your case, there are words that belong to the language, but your machine may loop forever
think in this way, by setting $A$ to be all languages, $A \setminus B$ is basically a complement of $B$
@dtldarek You mean that the machine that I have drawn is wrong?
14:02
@dtldarek Should it be like that?
Let me ask you a question, is the language related to the halting problem RE?
And the second question: is its complement RE?
@dtldarek The halting problem is recursive enumerable, but not decidable.

No, its complement isn't RE, otherwise it would be recursive.
great
Now, can you guess how does it relates to $A \setminus B$?
14:19
@dtldarek You mean that we can reduct the halting problem $H=\{ (n,x)| T_n(x) \downarrow \}$ to $A \setminus{B}$ ?
So by taking as $A$ to be all the languages, we have that $A \setminus{B}=B^c$.

$B^c$ is the set $\{ x \in A: x \notin B\}$. How can we reduct $H$ to $B^c$ ?
We would like to use $H^c$, which isn't RE.
In other words, set B = H.
Why can we just set B=H ?
Ok, suppose that given that $A$ and $B$ are RE, then $A \setminus B$ are RE as well. $H$ is RE, so by our assumption we have that $H^c$ is RE too, but that would make $H$ decidable.
Ah I see now what you mean. So is the set that contains all the languages recursively enumerable? @dtldarek
Well, can you construct a Turing machine that recognizes whether the element is in the set or not?
14:32
Yes, and in our case the elements are languages, i.e. sets, right? @dtldarek
Then how can we deduce that the set of all the languages is recursively enumerable? @dtldarek
We don't need a set that contains all the languages, only the "full" language
perhaps my phrase "set $A$ to be all languages" confused you
I meant the full language there
What do you mean with full language? all the recursively enumerable languages?
I mean $\Sigma^*$
14:51
@dtldarek Aha... So we fix an alphabet, say $\Sigma=\mathbb{N}$, right? Then do we consider as $H$ this set $H=\{ n \in \mathbb{N} \mid T_n(n) \downarrow \}$ , so that the latter is a subset of $\mathbb{N}$ ?
usually $\Sigma = \{0,1\}$, with infinite alphabets things get more complicated
and you represent $n$ as binary encodings
so yes, $H$ would be then considered a subset of all substrings on $\{0,1\}$
and the halting problem can be formulated as to guess if the given string belongs to that particular set of strings or not
(here guess = decide)
15:20
Great. I got it... Thanks a lot!!! :) @dtldarek
Can we also use it for example in this case $A \triangle B=(A \cup B) \setminus (A \cap B)$, where $A,B$ recursively enumerable?

Then we have that $A \cup B= \Sigma^{\star}, A \cap B=H$, then $A \triangle B=\Sigma^{\star} \setminus{H}=H^c$ which is not recursively enumerable.

So $A \cap B$ is not recursive, right?
for XOR you are correct
for $A \cap B$ by recursive you mean decidable?
Yes, that's what I meant.
then you are again correct, it is RE, but not R
Oh, I am sorry. I wanted to write $(A \cup B) \setminus{A \cap B}=H^c$ is not RE, and so also not decidable.

But like that we also show that $A \cap B=H$ is not decidable since $H^c$ is not RE. Right?
15:47
yes
Nice :) How can we check whether $AB$ is decidable given that A, B are RE?
$AB$ is defined like that: $\{ ab \mid a \in A, b \in B \}$, right?
do you mean concatenation of two languages?
Yes, I think that concatenation is meant.
How did you approach that problem?
If we would pick the same sets , i.e. $A= \Sigma^{\star}$, $B=H$, then $\Sigma^{\star}H=\{ ab \mid a\in \Sigma^{\star}, b \in H\}$.
But we do not know if there is a machine that computes this set. Because it can happen that the machine that computes $\Sigma^{\star}$ does not halt.
Or am I wrong?
15:57
$\Sigma^*$ is decidable
Oh yes, right.
A and B are recursively enumerable, and since A is decidable we have that AB is RE. Right?
in this particular case yes
but what about the general case?
both A and B are RE, but neither needs to be in R
Yes, in the genral case it holds what I said. The Turing machine that computes A does not halt necessarily and if it does not halt, we cannot take the union with the Turing machine that computes B. So we have to pick a set A such that with some input the machine does not halt. Right?
I think you should work on it a bit more
16:30
@dtldarek I thought now that we are just interested in the case when the machine of A halts, otherwise we cannot have the concatenation with an other string. So we take the machine that computes A and connect the arrows with the output yes, to the machine that computes B. So $AB$ is RE. Right?
yes
Still, you have to be careful
depending on your precise definition, the machine you will need to construct might look differently
for example there might be duplicates
and you do not know at first which part of the word comes from A and which from B
(if you are using the definition that tries to recognize a single word)
Oh yes, right. So we cannot give a general description of the Turing machine of the concatenation, can we?
We can
only you need to handle a few more things
16:47
So we take cases if $B \subset A$, $B \not\subset A \text{ but } A \cap B \neq \varnothing$ and $B \cap A =\varnothing$ ?
17:24
I need to go, sorry
Try to figure out this one on your own.
Bye!

  last day (16 days later) »