# Classify the set of all TMs whose languages from the accepting problem

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

• 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. – Shaull May 28 '16 at 7:56
• Well, it was briefly mentioned so it's not the first time I hear the term. I'll dive into it. Thankes! – Uria Mor May 28 '16 at 8:11
• 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. – Raphael May 28 '16 at 9:28
• No... it was a mistake. Ive edited accordingly. Thankes! – Uria Mor May 28 '16 at 9:31
• See the extended version of Rice's theorem, cs.stackexchange.com/a/11289 (sec 4.1) – Ran G. May 28 '16 at 14:11

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