Is it possible to proof for a Language L and its L-complemented to be both not recursively enumerable? Can be useful to consider the (Ld) diagonalization Language? thank you.
1
-
$\begingroup$ Are you trying to find such an $L$ or just trying to prove such $L$ exists? $\endgroup$– xskxzrCommented Jun 11, 2018 at 11:38
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
AS you know the number of Turing machines is countable while the number of subsets of sigma star is uncountable , so definitely the number of languages that are not recursively enumerable is uncountable. If the complement of all such languages is recursivelu enumerable, so their complement should have Turing machine, that this means that the number of languages that is not recursively enumerable but their complement is recursively enumerable, is countable,
so we have so many languages that both the language and its complement is not recursively enumerable, and the set of such languages is uncountable.
$\begingroup$
$\endgroup$
By the Rice-Shapiro theorem, both these sets are not recursively enumerable.
$$ \begin{array}{l} L= \{ n \ |\ \mathrm{dom}(\varphi_n) \mbox{ is finite} \} \\ \bar L= \{ n \ |\ \mathrm{dom}(\varphi_n) \mbox{ is infinite} \} \end{array} $$
If you want languages instead of sets, you can adapt the above to sets of encodings of Turing machines.
Another language which is not RE and has a non RE complement is
$$ L = \{0\langle M \rangle \ |\ M \mbox{ halts on empty input}\} \cup \{1\langle N \rangle \ |\ N \mbox{ does not halt on empty input}\} $$
Indeed, it is easy to reduce the halting problem to both $L$ and $\bar L$, and then prove that neither is RE.
