1

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?

Tree Garen
  • 709
  • 5
  • 15

1 Answers1

0

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

J. Dunivin
  • 3,103