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 $&gt; |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!
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:


M is a Non-Deterministic TM
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:


M isn't an NDTM, OR
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.