TITLE: NEGATE this statement: if $L(M) = \emptyset$, then for any $w$, $M$ halts on $w$ implies $M$ loops on $ww$
QUESTION [1 upvotes]: if $L(M) = \emptyset$, then for any $w$, $M$ halts on $w$ implies $M$ loops on $ww$
M is a turing machine.
my attempt
First I'm trying to simplify this using $A \to B = not A \lor B$
$\Leftrightarrow L(M) \neq \emptyset$ or for all $w$, $M$ halts on $w$ implies $M$ loops on $ww$
$\Leftrightarrow L(M) \neq \emptyset$ or for all $w$, M loops on w or M halts on $ww$
Now to negate this
$L(M) = \emptyset$ and there exist $w$ such that $M$ halts on $w$ and $M$ loops on $ww$.
Is this right?

REPLY [0 votes]: I'm not sure how you transitioned from $M$ loops on $ww$ to $M$ halts on $ww$. 
We agree that $p \implies q \iff \neg p \lor q$, so 
$$M \text{ halts on } w \implies M \text{ loops on } ww \iff M \text{ loops on } w \text{ or } M \text{ loops on } ww .$$ 
So the statement to negate is, "$L(M)\neq\emptyset$ or for all $w$, $M$ loops on $w$ or $M$ loops on $ww$", which results in 
$$\textbf{Negation: } L(M) = \emptyset \text{ and there exists a } w \text{ such that } M \text{ halts on } w \text{ and } M \text{ halts on } ww.$$ 
Equivalently, you could say that there exists a $w$ such that $L(M)=\emptyset$ and $M$ halts on $w$ and $ww$.
{"set_name": "stack_exchange", "score": 1, "question_id": 3321524}