4
$\begingroup$

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.

Thanks in advance

$\endgroup$

1 Answer 1

5
$\begingroup$

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}$.

$\endgroup$
5
  • $\begingroup$ Why do all machines that halt on no input accept the empty set? Why can't a TM accept on the empty word? $\endgroup$
    – sadcat_1
    Feb 10 at 15:58
  • $\begingroup$ @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$. $\endgroup$
    – Knogger
    Feb 10 at 16:07
  • 3
    $\begingroup$ My bad, I read "halt on no input" as "halt on empty word $\varepsilon$". Thank you for your answer. $\endgroup$
    – sadcat_1
    Feb 10 at 16:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – Stef
    Feb 11 at 10:21
  • $\begingroup$ @Stef & sadcat_1 Thanks for the feedback! Yeah, I can see how my phrasing was ambiguous, I'll fix it right away. $\endgroup$
    – Knogger
    Feb 11 at 10:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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