0

As stated in title I want to determine to which class

$$S=\left\{\langle M\rangle\Big\vert L(M)\in RE\setminus R\right\}$$

belongs. I believe that $S\notin RE\cup\text{co}RE$.

  1. In order to show that $S\notin RE$ I tried to reduce $\overline{H_{TM}}$ to $S$ using the fact that $\overline{H_{TM}}\notin RE$

  2. In order to show that $S\notin \text{co}RE$ I tried to reduce $H_{TM}$ to S using the fact that $H_{TM}\notin \text{co}RE$.

In both cases I got stuck with defining $M'$ and what it should do.

How should I construct the reduction? Thank you!

Galc127
  • 4,451
  • Is $S = { \langle M \rangle \mid L(M) \in RE ;\backslash R }$ the language consisting of all Turing Machines whose languages are "Recursively Enumerable" but not "Recursive"? – user137481 Jun 01 '16 at 15:48
  • @user137481, exactly. – Galc127 Jun 01 '16 at 15:49
  • If you want to pin down where $S$ lies more closely, it is $\Pi^0_3$ complete. It isn't clear whether you need to decide more than whether $S$ is recursive, RE, coRE or none of the above. – James Jun 01 '16 at 16:37

0 Answers0