0

L = {M, w| M is a TM, w is a string, and for some nonempty strings x, y, w = xy, M accepts xyx and M rejects yxy}..

Im having issues representing this in mathematical form.

For example what would the negation of "M accepts xyx" be? or "for some nonempty strings x, y, w = xy,"

How would I negate this?

user126885
  • 159

1 Answers1

1

I'm not sure what you mean by "representing this in mathematical form," but I'll try to help with quantifiers.

To answer your two questions:

Negating "$M$ accepts $xyx$"

There are three possibilities for a Turing Machine on any input: accept, reject, or "run forever" (not halt). So, the negation of "$M \text{ accepts } xyx$" corresponds to "$M$ rejects $xyx$ or $M$ does not halt on $xyx$."

Negating "for some non-empty strings $x$, $y$, $w = xy$"

By "for some," are you saying "for all" or "there exist"?

It sounds like "for some non-empty strings $x$, $y$, $w = xy$" is actually "for $\textit{all}$ non-empty strings $x$, $y$, where $w = xy$". In general, the negation of a statement of the form

$$\text{for all } x_1, x_2, ... , x_n, S$$

(where $S$ is some statement) is the statement

$$\text{there exist } x_1, x_2, ... , x_n | \neg S$$

Where "|" indicates "such that." The reasoning behind this is that the opposite of "this rule always applies" is "there exists a counterexample to this rule."

So in your case, you would be negating "for all non-empty strings $x$, $y$, where $w = xy$, $M$ accepts $xyx$ and $M$ rejects $yxy$." By the rule above, our negation is "there exist non-empty strings $x$, $y$, where $w = xy$, such that $M$ does not accept $xyx$ or $M$ does not reject $yxy$."

Note that the meanings of "$M$ does not accept $xyx$" and "$M$ does not reject $yxy$" have been explained above, and that "$M$ does not accept $xyx$ or $M$ does not reject $yxy$" is the result of De Morgan's law.

Community
  • 1
theyaoster
  • 2,068
  • I was told:The negation of "M accepts xyx" is not "M rejects xyx". Thats what confuses me – user126885 Aug 05 '16 at 17:55
  • Indeed, since $M$ doesn't have to reject $xyx$ to not accept $xyx$: $M$ could also not halt on $xyx$. Do you mean you were told that the negation of "$M$ accepts $xyx$" is "$\neg (M$ rejects $xyx)$? If so, I would say this is wrong, unless there is some hidden assumption that $M$ always halts. – theyaoster Aug 05 '16 at 17:59
  • Reject is not the same as negation of accept, M could've not accepted and not rejected at the same time. The correct negation would be M failed to accept. @user126885 – Ahmed S. Attaalla Aug 05 '16 at 18:02
  • No I wasnt told what the negation of M accepts xyx was. when I suggested that perhaps reject could be the negation, I was told that it was incorrect. – user126885 Aug 05 '16 at 18:03
  • I see. In that case, Ahmed's comment should clear things up. – theyaoster Aug 05 '16 at 18:05
  • @AhmedS.Attaalla so the correct negation for accepts would does not accept(Which means 1 of 2 things can occur? It loops or it rejects) correct? In that case for both statements I would say M failed to accept or M failed to reject. Which in turn implies that all three cases could occur – user126885 Aug 05 '16 at 18:06
  • In answer to your first question: yes, it loops or rejects. As for your second question: not quite, since the full statement is "$M$ accepts $xyx$ and $M$ rejects $yxy$," and it is not guaranteed that $xyx = yxy$. So, you should say "$M$ fails to accept $xyx$ or $M$ fails to reject $yxy$." – theyaoster Aug 05 '16 at 18:16
  • Sorry for being a bit unclear, M fails to accept xyx or MM fails to reject yxy is similar to saying(M loops on or rejects xyx OR M loops on or accepts yxy) Correct? So @BrianYao that would mean that this question would not be recognizable, because how could the machine potentially accept or loop on the same xyx – user126885 Aug 05 '16 at 18:22
  • For your first question: yes, that is correct. For your second question: not necessarily. When we say that $M$ accepts $xyx$ OR $M$ does not halt on $xyx$, we do not mean to say that both necessarily occur (that would be an AND statement, not an OR statement like we have here). The OR statement just claims that at least one of those two possibilities will occur. – theyaoster Aug 05 '16 at 18:31