a hard mapping reduction problem

Question

let L={(M1),(M2)|M1,M2 are TM's and L(M1)={(M)| M is a TM and M2 accepts (M)}} so my guess is L is not in RE but im having a hard time finding the right mapping reduction....any ideas ?

Answer 1

You are right, it is not RE. Reduction $EMPTY \le_m L$, where $ EMPTY=\{<M>| M \space is \space TM,L(M)=\emptyset\}$, can be done like this: $$ f(<M>)=<M>,<M_{reject}> \space \space where \space L(M_{reject})=\emptyset$$

Similarly it could be done from $co-HALT$, but we do not have to change input TM at all if we do it from $EMPTY$.

Answer 2

Let R be a recognizer for L and construct the following machine,

NON-HALT = "On input $<A>$, w
$\quad\quad\quad\quad\quad\quad\quad1. <M1>$ = "On input x
$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$reject "
$\quad\quad\quad\quad\quad\quad\quad2. <M2>$ = "On input x
$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$ Run A on w"
$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$ accept"
$\quad\quad\quad\quad\quad\quad\quad3. $ if R accepts $<M1, M2>$
$\quad\quad\quad\quad\quad\quad\quad\quad\quad$ accept
$\quad\quad\quad\quad\quad\quad\quad\;\;$ otherwise
$\quad\quad\quad\quad\quad\quad\quad\quad\quad$ reject"

In line 1, $<M1>$ is constructed so that L($M1$) = $\emptyset$
In line 2, $<M2>$ is constructed so that L($M2$) = $\emptyset\quad$ iff A loops on w
In line 3:
$\quad\quad$R accepts $<M1, M2>$
$\quad\quad\Leftarrow\Rightarrow \emptyset = \{<M>|\;$M is a TM and M2 accepts M$\;\}$
$\quad\quad\Leftarrow\Rightarrow L(M2) = \emptyset$
$\quad\quad\Leftarrow\Rightarrow$ A loops on w

If R exists, NON-HALT would be a recognizer for the non-halting problem.
This would be a contradiction that the non-halting problem is not recognizable.
So, L must be RE.