dtldarek

(Sorry I was not much help!)

It's late, I need to go, bye!

now it worked :-|

The M_R machine does something like this: 1. move left, 2. if blank do some finishing steps. 3. if not blank: remember "in a state" what letter we got, mark the current location with a blank (so that we know where to go back), 4. go just after the second blank right, put in the letter that we read, go back to second blank to the left (that would be our marked position), replace our blank-marker with proper letter that was there. 5. repeat (we start with one step to the left).

Then I suppose also that "l" is kne step left, "r" is one step right and "b" is put blank here.

Test test it seems I cannot send anything :-(

Sorry, but I do not understand this notation.

Sure, I will take a look, give me a moment.

Sure, I don't know if I will be able to answer, but you can ask :-)

Bye!

Try to figure out this one on your own.

I need to go, sorry

only you need to handle a few more things

We can

(if you are using the definition that tries to recognize a single word)

and you do not know at first which part of the word comes from A and which from B

for example there might be duplicates

depending on your precise definition, the machine you will need to construct might look differently

Still, you have to be careful

yes

I think you should work on it a bit more

both A and B are RE, but neither needs to be in R

but what about the general case?

in this particular case yes

$\Sigma^*$ is decidable

How did you approach that problem?

do you mean concatenation of two languages?

yes

then you are again correct, it is RE, but not R

for $A \cap B$ by recursive you mean decidable?

for XOR you are correct

(here guess = decide)

and the halting problem can be formulated as to guess if the given string belongs to that particular set of strings or not

so yes, $H$ would be then considered a subset of all substrings on $\{0,1\}$

and you represent $n$ as binary encodings

usually $\Sigma = \{0,1\}$, with infinite alphabets things get more complicated

I mean $\Sigma^*$

I meant the full language there

perhaps my phrase "set $A$ to be all languages" confused you

We don't need a set that contains all the languages, only the "full" language

no

Well, can you construct a Turing machine that recognizes whether the element is in the set or not?

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.

In other words, set B = H.

We would like to use $H^c$, which isn't RE.

Now, can you guess how does it relates to $A \setminus B$?

great

And the second question: is its complement RE?

Let me ask you a question, is the language related to the halting problem RE?

yes