# Proving a language is not Turing-recognizable by reduction from $D = \{\langle M\rangle \mid M \text{ rejects input }\langle M\rangle\}$

I'm having a really hard time understanding some of these concepts. I've read them over from several different sources and still can't reach the a-ha moment.

I need to prove a language $L$ is not Turing-recognizable by giving a reduction from the following language:

$$D = \{\langle M\rangle \mid M \text{ rejects input }\langle M\rangle\}\,,$$

where $M$ is a Turing machine, and $\langle M\rangle$ is a binary encoding of $M$, and it is already assumed $M$ is neither decidable nor recognizable.

Most of the things I've read show how to prove a language is undecidable, but not unrecognizable. How would it be different?

I've encountered the following that I feel I can modify for my problem:

$$\mathrm{A_{TM}} = \{\langle M,w\rangle \mid M \text{ accepts }w\}\,.$$

$D$ reduces to $\mathrm{A_{TM}}$. Consider the computable function that maps $\langle M\rangle$ to $\langle M',w\rangle$, where $w=\langle M\rangle$ and $M'$ is a machine that accepts if and only if $M$ rejects. Therefore, $\mathrm{A_{TM}}$ is undecidable.

But I'm not really sure how to understand it, in plain English. Could someone explain it? Plus, how could I change this to show $\mathrm{A_{TM}}$ is unrecognizable (even if it is recognizable)?

• I'm not sure what you're asking. It seems you've been asked to prove that some langauge $L$ is not recognizable by reducing $D$ to it. Are you asking how to reduce $D$ to $L$, or asking how reducing $D$ to $L$ proves that $L$ is not recognizable? What you've written after "I've encountered" doesn't seem very much connected to either of those things. – David Richerby Mar 14 '15 at 18:37
• I am asking for better intuition on the steps needed to reduce a language to another to prove it is not recognizable. ATM is very closely related to the language L I need to prove is not recognizable. However, the reduction given from D to L is to prove how ATM is not decidable. – Tanner Mar 14 '15 at 18:48
• "I've read them over from several different sources and still can't reach the a-ha moment." -- Myself, I've reached these moments by thinking (rarely) or doing (usually), not reading. – Raphael Mar 14 '15 at 18:54
• I suspect that this is fully answered by this answer to one of our reference questions. – Raphael Mar 14 '15 at 18:55
• @Raphael my problem is that I must be thinking about things the wrong way, because I am getting nowhere. – Tanner Mar 14 '15 at 19:04

Like any claim, you have more than one way to prove a language $L$ is unrecognisable.

In case your language is in $Co-RE$ you can do one of the following:

1. Show $\overline{L}$ is in $RE$ by describing a TM that accepts $\overline{L}$.
2. Show $\overline{L}$ is in $RE$ by reduction $\overline{L}\le_m Some-Language-In-RE$.
3. Show $\overline{H_{TM}} \le_m L$ or $\overline{A_{TM}} \le_m L$ or some other language you know is in $Co-RE$

Note that you must show that $L\notin R$ in order to deduce $L\notin RE$.

If $A\notin Co-RE$, you can show a reduction to your language

1. $A\le_m L$ where $A\notin RE$ so if $L\in RE$ you have a contradiction.

There is more than one way. I'm not sure I understand your question, but if your task is to show $D\notin RE$. I would show $\overline{D}\in RE$, and than show $D\notin R$.