My intuition is that $L\notin coRE$, but I haven't managed to prove that $HP \le L$, as previously I only saw reductions from $HP$ or from $\overline{HP}$ with $f$ such that $f((\langle M\rangle,x))=\langle M_x\rangle$, while $M_x$ performs some simulation of $M$ on $x$.

(The answer eluded me for some time, so I started writing a question here. After I found the surprisingly simple answer, I decided to post it (Q&A-style) anyway.)


We would show that $HP \le L$.

Let $f:\Sigma^*\rightarrow \Sigma^*$ be a function such that for any $x\in \Sigma^*$: $$f(x)=\langle M_x\rangle$$ while $M_x$ is a TM that accepts $x$ and rejects every other word.

$f$ is computable, as it only requires writing the encoding of a very simple TM.

Now, for any $x\in \Sigma^*$:

  • $L(M_x)=\{x\}$
  • If $x\in HP$, then $\{x\}\subseteq HP$, and so $\langle M_x\rangle \in L$.
  • Otherwise, $x\notin HP$, and then $\{x\}\not\subseteq HP$, and so $\langle M_x\rangle \notin L$.

Therefore, indeed $HP \le L$.

Thus, it must be that $L\notin coRE$, because otherwise the reduction would imply that $HP\in coRE$, which is false.


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.