Recognizability of $\left\{ \left\langle M\right\rangle |M\text{ is a TM and }A_{TM}\leq\mathcal{L}\left(M\right)\right\} $

Question

Determine whether the following language is decidable, recognizable but not decidable, co-recognizable but not decidable or neither recognizable nor co-recognizable. Prove your answer. $$L=\left\{ \left\langle M\right\rangle |M\text{ is a TM and }A_{TM}\leq\mathcal{L}\left(M\right)\right\} $$

[Where $\mathcal{L}(M)$ is the set of words accepted by $M$ and $A_{TM}\leq L$ if there is a mapping reduction from $A_{TM}$ to $L$]

So if I understand correctly the question is whether the set of all $\mathcal{RE}$-hard languages is recognizable/co-recognizable. It seems an easy corollary of Rice's theorem that it is not decidable, and my intuition tells me it is neither recognizable nor co-recognizable but I'm having issues contradicting any reductions.

My approach was, to show it is not recognizable, to assume it is and therefore there is a reduction $L\leq A_{TM}$, where given a TM $M$ recognizing it we would run $M(<M>)$ where I hoped to get some diagonalization argument, but I failed.

Edit: I was able to show that $L\not\in co\mathcal{RE}$, using a reduction $A_{TM,\varepsilon}\leq L$. Given an encoding of a Turing machine $\left\langle M\right\rangle$ define $f\left(\left\langle M\right\rangle \right)$ to be the Turing machine which on input $\left\langle M',w\right\rangle$ :

For $i$ from $1$ to $\infty$:

• Run $\left\langle M',w\right\rangle$ for $i$ steps.
• Run $\left\langle M,\varepsilon\right\rangle$ for $i$ steps.
• Accept if both accepted.

I wasn't able to modify this to show $L$ is not recognizable though, wanted to do a similar reduction using $\overline{A_{TM,\varepsilon}}$, but I have issues either getting a recognizable language when $M$ doesn't halt, as the "common" method of running for $|w|$ steps only produces decidable languages.

Answer 1

The reduction you suggest can be a bit simplified, by running the machines serially rather than "in parallel". That is, First check if $M$ accepts $\epsilon$, and if it does, run $M'$ on $w'$.

Your idea is to make sure that if $M$ accepts $\epsilon$, then the language of $f(\langle M\rangle)$ is $A_{TM}$, and otherwise it's empty.

We can do a similar thing to show that the language is not in RE, but it requires a bit more subtlety:

We show that $A_{\overline{TM,\epsilon}}\le_m L$ as follows. Given $\langle M \rangle$, the reduction outputs a machine $f(\langle M \rangle)$, which on input $\langle M',w' \rangle$ works as follows:

1. Simulate the run of $M$ on $\epsilon$ for $|\langle M',w' \rangle|$ steps.
2. If $M$ does not accept $\epsilon$ during that simulation, simulate $M'$ on $w'$ and answer whatever it answers.
3. Otherwise, if $M$ accepts $\epsilon$ during that simulation, reject.

Now, the crux of the construction is in step 1, where we simulate for a finite number of steps, but this number depends on the input, so it can grow arbitrarily large.

What we get is that if $M$ does not accept $\epsilon$, then we'll always get to step 2, so $L(f(\langle M\rangle))=A_{TM}$, and all is well.

However, if $M$ does accept $\epsilon$, then we get something a bit strange - for some small inputs, it may still be the case that we'll get to step 2. But for large enough inputs, we'll get to step 3. This means that $L(f(\langle M\rangle))$, so clearly there is no reduction from $A_{TM}$ to it, and we're done.