A mapping reduction to show that L is unrecognizable and so it's complement

Question

I am having hard time proving that $$ L = {<M,x,y> | M \, halts \, on\, xy\, and\, M\, doesn’t \,halt\, on\, yx} $$ is not recursively enumerable and also it's complement. Any idea on a way to solve it?

Thanks a lot

Answer 1

Let $HP = \{\langle A,s \rangle :$ A is a TM that halts on s $\}$
and $\overline{HP} = \{\langle A,s \rangle :$ A is a TM that does not halt on s $\}$

Suppose $R$ is a recognizer for $L$.
The following reduction shows that $L$ is not Turing-Recognizable

Loop = "On input <A, s>:
        1) M = "On input <w>
                10) if w = '01'
                20)     accept
                30) else
                40)     simulate A on s
        2) if R accepts <M, 0, 1>
        3)     accept
        4) else
        5)     reject

R accepts $\langle M, 0, 1 \rangle \; \Leftarrow\Rightarrow \langle M \rangle \in \; L \Leftarrow\Rightarrow A$ loops on s

If R recognizes L then Loop recognizes $\overline{HP}$
Since $\overline{HP}$ is not recognizable, L is not Turing-Recognizable.

For the complement suppose $R$ is a recognizer for:
$\quad L' = \{\langle M,x,y \rangle :$ M loops on xy or M halts on yx $\}$

The following reduction shows that $L'$ is not Turing-Recognizable and hence that $L$ is not co-Turing recognizable.

Loop = "On input (A, x)
        1) M = "On input w
                10) if w = '01'
                20)     simulate A on s
                20) else
                50)    loop

        2) if R(M, 0, 1) accepts
        3)     accept
        4) else
        5)     reject

R accepts $\langle M, 0, 1 \rangle \; \Leftarrow\Rightarrow \langle M \rangle \in \; L' \Leftarrow\Rightarrow A$ loops on s

If R recognizes $L'$ then Loop recognizes $\overline{HP}$
Since $\overline{HP}$ is not recognizable, $L'$ is not Turing-Recognizable.
Hence, $L$ is not co-Turing-Recognizable