1
$\begingroup$

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)?

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ Mar 14, 2015 at 18:37
  • $\begingroup$ 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. $\endgroup$
    – Tanner
    Mar 14, 2015 at 18:48
  • $\begingroup$ "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. $\endgroup$
    – Raphael
    Mar 14, 2015 at 18:54
  • $\begingroup$ I suspect that this is fully answered by this answer to one of our reference questions. $\endgroup$
    – Raphael
    Mar 14, 2015 at 18:55
  • $\begingroup$ @Raphael my problem is that I must be thinking about things the wrong way, because I am getting nowhere. $\endgroup$
    – Tanner
    Mar 14, 2015 at 19:04

1 Answer 1

3
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.