# Is the language L = {<M> | There exists an M' that stops on the same input words, but L(M) ≠ L(M')} in RE or R?

Is the language $$L = \{M | \exists M' \text{ that stops on the same input words but L(M)} \neq L(M')\}$$ in RE or R?

I suspect that it's not in RE, since you'd have to first know for M all the inputs for which it halts, which you can't do in a finite time.

I wanted to show that $$\overline {HP} \leq L$$, and so because $$\overline {HP} \notin RE$$, also $$L \notin RE$$, but I can't seem to find a reduction function.

Notice, that all machines $$M$$ that don't halt on any input accept the same language, $$\emptyset$$. Thus if $$M$$ doesn't halt on any input then also $$\langle M \rangle \notin L$$.

Now define the TM $$M'$$ for some TM $$M$$ such that on input $$x$$

• $$M'$$ runs $$M$$ on $$x$$
• $$M'$$ rejects if $$M$$ halts accepting
• $$M'$$ accepts if $$M$$ halts rejecting

It's easy to see, that $$M \text{ halts on } w \iff M' \text{ halts on } w$$ and that $$L(M) \neq L(M')$$ for all machines $$M$$ that halt on some input. From this it follows that, if $$M$$ halts on some input, then $$\langle M \rangle \in L$$.

With this we have shown that $$L = \{\langle M \rangle : M \text{ halts on some input}\}.$$ This language is known to be in $$\texttt{RE} \setminus \texttt{R}$$.

• Why do all machines that halt on no input accept the empty set? Why can't a TM accept on the empty word? Commented Feb 10 at 15:58
• @sadcat_1 There's no universal definition for TMs, but in general we define acceptance in a TM such that a machine $M$ accepts iff $M$ halts in an accepting state. So if $w \in L(M)$ then $M$ must have stopped on $w$. Therefore if $M$ doesn't halt on any $w$ then it can't have accepted anything, so $L(M) = \emptyset$. Commented Feb 10 at 16:07
• My bad, I read "halt on no input" as "halt on empty word $\varepsilon$". Thank you for your answer. Commented Feb 10 at 16:51
• I also read "halt on no input" as "halt on empty word". Maybe "doesn't halt on any input" would be less prone to this interpretation.
– Stef
Commented Feb 11 at 10:21
• @Stef & sadcat_1 Thanks for the feedback! Yeah, I can see how my phrasing was ambiguous, I'll fix it right away. Commented Feb 11 at 10:29