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.

  • $\begingroup$ Your intuition is correct. Try to follow the proof of Rice theorem to gather some elements that can be used in reductions, and then try to directly reduce some unrecognizable/un-corecognizable language to L. $\endgroup$ – Shaull Jun 14 '17 at 9:55
  • $\begingroup$ @Shaull I tried, but am actually still stuck on this. $\endgroup$ – Nescio Jun 21 '17 at 8:00

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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