# Classification of the complement of a language

$L = \{ \langle M \rangle \mid M \text{ accepts two strings of different lengths} \}$.

What is complement of this language?

my attempt:

the complement is: $M$ accepts no two strings of same length and this can be done by dovetailing different inputs on M but we can never say IT CANNOT ACCEPT TWO STRING OF SAME LENGTH and hence its NOT RECURSIVELY ENUMERABLE?

The complement of $L$ is:
$\bar{L} = \{\langle M \rangle \mid \text{ all strings accepted by$M$have the same length} \}$
Your intuition that $\bar{L}$ is not recursively enumerable is correct, it is in fact complete for $\Pi^0_1$ by reduction from the emptiness problem. If you only need to prove that $\bar{L}$ is not in $\textsf{RE}$, it is sufficient to observe that $L$ is undecidable (reduction from the halting problem) but $\textsf{RE}$ (trivial).
• You can prove the undecidability of $L$ by other means, e.g. the Rice Theorem. – quicksort Jan 7 '18 at 15:17
The complement of $L$ is $$\overline{L} = \{\langle M \rangle \mid |L(M)|>1 \implies \text{ all strings of } L(M) \text{ have the same length}\}$$ In words, $L$ consists of those TM $M$ such that either $L(M) = \emptyset$, or $L(M)$ has only one string, or all strings in $L(M)$ have the same length.
$L$ is recursively enumerable. Given $\langle M \rangle$ you can use dovetailing to search for two strings in $L(M)$ of different length, and accept $\langle M \rangle$ as soon as you find a single pair. You can solve yourself if $\overline{L}$ is recursively enumerable or not.