1
$\begingroup$

I'm trying to construct a reduction from $A \in RE \setminus R$ under $\sum=\{0,1\}$ to $B$ which defined: $B=\{0w:w \in A\} \cup \{1w: w \notin A \}$.

I need to show that $B\notin RE \cup co-RE$ with the the defining of $A$ and the use of the theorem that says:

if $L \notin R$ and $\bar{L} \leq_ML$ so $L \notin RE \cup co-RE$

so I though of showing a reduction form A to B which will tell me that $B\notin R$ and to show a reduction from $\bar{B}$ to $B$.

First I have a problem with the following attempt:

Given $M$ Turing for A, Let's construct a Turing machine $M'$ for B:

given input $w$ for $M'$:

simulate $w$ on $A$, if it accepts, $M'$ accepts $0w$, otherwise $M'$ accepts $1w$.

It's not correct, isn't it? since what happens if $M$ stuck in a loop?

Suggestions for correctness? Is it a good plan for this question?

Thanks!

1 Answers 1

4

You should (or at least can) work by contradiction. First assume that $B$ is r.e. and show that this implies that $A$ is computable. Then assume $B$ is co-r.e. and show that this also implies that $A$ is computable. Thus you will be reducing $A$ to $B$, and reducing $A$ to the complement of $B$, rather than reducing $B$ to $A$ as suggested in the sketch at the end of the question.

Note that to prove $B$ is not r.e. or co.r.e., it is only necessary to assume that $A$ is not computable, it is not necessary to assume $A$ is r.e. However, one reason that this result is interesting is that you can go farther and prove that $A$ and $B$ are Turing equivalent. So if we do take $A$ to be r.e. but not computable, we get an example of two sets $A$ and $B$ that are Turing equivalent, while $A$ is r.e. and $B$ is not.