0
$\begingroup$

Let $$L = \{ \langle M \rangle \mid M \text{ is a Turing machine so } A_{TM} \leq_m L(M) \}$$ The question is whether $L$ is in $\mathcal{R}, \mathcal{RE}, co-\mathcal{RE}$ or in $\overline{\mathcal{RE} \cup co-\mathcal{RE}}$ ?





I gained some progrees showing $L \notin co- \mathcal{RE}$:
Define reduction $f:A_{TM}\rightarrow L$ on input $\left\langle M,w\right\rangle$ returns:

  • if $M$ accepts $w$ return $ \left\langle U_{TM}\right\rangle $ ($L \left(U_{TM}\right)=A_{TM}$ so $\left\langle U_{TM}\right\rangle \in L$)
  • if $\left\langle M\right\rangle$ rejects $w$ return 1 (not a TM encoding hence not in L)

$f$ is computable and $\left\langle M,w\right\rangle \in A_{TM}\iff f\left(\left\langle M,w\right\rangle \right)\in L$ hence $A_{TM}\leq_m L \implies L\notin co-\mathcal{RE}$.

Now I want to show that $L \notin \mathcal{RE}$. And I'm stuck..

Notation:

$A_{TM} = \{ \langle M,w \rangle \mid M \text{ is a TM}, w \in L(M)\}$

$H_{TM} = \{ \langle M,w \rangle \mid M \text{ is a TM and $M$ halts on $w$} \}$

$\endgroup$
9
  • 2
    $\begingroup$ Are you familiar with the concept RE-hardness? Try to prove that $A_{TM}$ is RE-hard (in fact, RE-complete). This should lead you in the right direction. $\endgroup$
    – Shaull
    May 28, 2016 at 7:56
  • $\begingroup$ Well, it was briefly mentioned so it's not the first time I hear the term. I'll dive into it. Thankes! $\endgroup$
    – Uria Mor
    May 28, 2016 at 8:11
  • 1
    $\begingroup$ I'm not sure what your plan is with $\mathcal{C}$; it seems mostly unrelated to $L$. Or does $L_C$ denote its index set? Then you'd still have to show that $\mathcal{C} \not\in \{\emptyset, 2^{\Sigma^*} \}$ before you can apply Rice's theorem. $\endgroup$
    – Raphael
    May 28, 2016 at 9:28
  • $\begingroup$ No... it was a mistake. Ive edited accordingly. Thankes! $\endgroup$
    – Uria Mor
    May 28, 2016 at 9:31
  • $\begingroup$ See the extended version of Rice's theorem, cs.stackexchange.com/a/11289 (sec 4.1) $\endgroup$
    – Ran G.
    May 28, 2016 at 14:11

1 Answer 1

1
$\begingroup$

As suggested in the comments, the extended version of Rice's theorem clearly states this language is not in $RE$. Nevertheless, let us prove this claim via a direct reduction from a language known not to be in $RE$, let's say $$ \overline{HP} = \{\langle M,w\rangle \mid M \text{ doesn't halts on }w \}$$

We will show that $\overline{HP} \le L$ and conclude that $L \notin RE$.

The reduction will assume we have a machine that recognizes $A_{TM}$ (call it $R$) and goes as follow. Given an input $\langle M,w\rangle$ we construct the output string $\langle M_w\rangle$ which is a machine that, on input x, does:

  1. repeat the loop:
    1.1 run one step of $M$ on $w$
    1.2 run one step of $R$ on $x$
    1.3 if 1.1 halts - the machine $M_w$ rejects. If 1.2 accepts - the machine $M_w$ accepts.

It is easy to verify this is a computable reduction. Let's just verify it is valid.

Case I: $\langle M,w\rangle\notin \overline {HP}$, then eventually (say after $T$ steps) $M$ will halt on $w$ before the computation of 1.2 concludes, thus $L(M_w)$ can be decided in less then $T$ steps and in particular it is decidable. Therefore $A_{TM} \not\le L(M_w)$ and thus $\langle M_w\rangle \notin L$.

Case II: $\langle M,w\rangle\in \overline {HP}$, then $M$ never halts on $w$, which means that only step 1.2 is relevant, which means that $M_w$ behaves in this case just like $R$. So it holds that $L(M_w) = A_{TM}$ and in particular, $A_{TM} \le L(M_w)$. Then, $\langle M_w \rangle \in L$.

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