# How to define (logically) the complement language?

I found it a little bit difficult and confusing to define the complement language in specific cases. For example, take the next language:

$$L = \left\{\langle M, w\rangle \;\middle|\; \begin{array}{l}M \text{ is a Non-Deterministic TM,}\\ \text{and it has an accepting run on }w\text{ of length }\leq |w|\end{array}\right\}\,.$$

When I've tried to find $$L$$-complement I did it like this:

M isn't an NDTM OR it doesn't have an accepting run on $$w$$ of length $$> |w|$$.

My way of thinking is to change each one of the quantifiers. Is that OK? Someone can write the logic behind that (I want to understand for other cases as well, this language isn't critical right now)?

Thanks!

This is just the application of de Morgan's laws: \begin{align*} \neg(A\land B) &\equiv (\neg A)\lor (\neg B)\\ \neg(A\lor B) &\equiv (\neg A)\land (\neg B)\,. \end{align*} These are fairly obvious, if you think about them for a moment: if something isn't both $$A$$ and $$B$$, then it must fail to be one or the other (or both); if something is neither $$A$$ nor $$B$$, then it is not $$A$$ and it is not $$B$$.

In your case, $$A$$ is "it is a NTM" and $$B$$ is "it has an accepting run on $$w$$ of length at most $$|w|$$." Using the first version of the law, the complement is "it is not an NTM or it does not have an accepting run on $$w$$ of length at most $$|w|$$."

That alone may be enough to answer the question, but you might also want to push the negation in the second half ("it does not have an accepting run on $$w$$ of length at most $$|w|$$"). In this case, we need the rules for negating quantifiers: \begin{align*} \neg\forall x\,C(x) &\equiv \exists x\,\neg C(x)\\ \neg\exists x\,C(x) &\equiv \forall x\,\neg C(x)\,. \end{align*} Again, take a moment to convince yourself that these are true: if it's not true that everything is $$C$$, it must be that something is not $$C$$; if there doesn't exist something that is $$C$$, then everything must be not $$C$$.

In your case, writing $$B$$ more formally gives "There exists a run $$r$$ on $$w$$ such that $$r$$ accepts and $$r$$ has length at most $$|w|$$", so $$C$$ is the property "is accepting and has length at most $$|w|$$." Negating $$B$$ gives "Every run $$r$$ on $$w$$ is not both accepting and of length at most $$|w|$$" and applying de Morgan again gives "Every run on $$w$$ is rejecting or has length more than $$|w|$$ (or both)."

• Thanks! I found the next still confusing: L = {<M, w>: M accepts w and uses at most |w| tape cells during the run on w}. The complement of this language is: M not accepts w OR don't use at most |w| tape cells during the run on w. Can the second part be like Use at least |w| tape cells (instead of at most?). – Roni Kurtberg Oct 1 '18 at 14:56
• @RoniKurtberg if something is not at most $x$ then it is more than $x$. – David Richerby Oct 1 '18 at 15:31
• But something is still confusing here. If we have a language with machines that halt on at least one input, the complement language is the machines that don't halt on at least one input (negate first property), or the machines that don't halt on at most one input (negate both properties)? – Roni Kurtberg Oct 2 '18 at 8:27
• @RoniKurtberg The complement is the machines that fail to have the property "halts on at least one input". If a machine fails to have the property "halts on at least one input" then, for every input, it must not halt. – David Richerby Oct 4 '18 at 10:31

You aren't exactly correct in your example because of the redundant negation of the $$\leq$$ sign. In the most general sense, we always have:

$$\neg (x_1 \land x_2\land ...\land x_n)=(\neg x_1) \lor...\lor (\neg x_n)$$

Meaning: NOT (A AND B AND C...) equals (NOT A) OR (NOT B) OR (NOT C)...

In your case, we have two conditions with an AND between them:

1. M is a Non-Deterministic TM

2. M has an accepting run on $$w$$ of length $$\leq |w|$$

Finding the complement of the language requires negating these conditions, and therefore getting the language where either:

1. M isn't an NDTM, OR
2. M is an NDTM , BUT, it doesn't have an accepting run on $$w$$ of length $$\leq |w|$$

Notice the difference in the negation of the second condition - we changed it from having a run satisfying a certain property to not having a run satisfying the same original property.

From my experience, usually in these kinds of questions you have a language composed of TMs/Automata/etc' fulfiling a certain condition, and in such cases the negation would be everything which isn't a TM/automaton/etc', PLUS everything which is of the correct "type" but doesn't fulfill the original given condition.

• Great! I'm wondering about the next language: L = {<M1, M2, w> | (M1&M2 both accepts w) OR (M1&M2 both rejects w) OR (M1&M2 both don't halt on w)}. What is L-complement in this case? Do we get an empty language? – Roni Kurtberg Sep 30 '18 at 13:41
• Negating OR is the opposite: $\neg (x_1 \lor ... \lor x_n) = (\neg x_1)\land ...\land (\neg x_n)$ In your case, we still have the possibility that one TM accepts and one rejects, or that one halts and one doesn't. – Dean Gurvitz Sep 30 '18 at 13:58