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

cs.stackexchange https://cs.stackexchange.com/questions/76767

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.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top