1
$\begingroup$

I am trying to prove that an undecidable language $L$ is not many one reducible to its complement.

The problem goes as follows: Formally prove that $L \not\leq_m \overline{L}$ for any undecidable $L$. ($\overline L$ is also denoted $L^c$.)

How would I go about proving this? I am unsure how to prove mapping reducibility, especially regarding any language.

I know I will need to use reduction here somehow. And I know that I will need to use the properties of L (like the fact that it is undecidable). Would I have to create a machine 𝑀 and 𝑀′ such that 𝑀 halts iff 𝑀′?

$\endgroup$
3
  • $\begingroup$ For the future, instead of deleting and re-posting your question, we'd prefer that you edit it based on the feedback you've received. $\endgroup$
    – D.W.
    Commented Oct 25, 2022 at 21:17
  • $\begingroup$ I'll repeat feedback that I gave before. We're not looking for questions that are just the statement of an exercise-style task and a request for us to tell you how to solve it. What did you try? Where did you get stuck? Did you try working through some examples? Do you know any examples of undecidable languages, and have you tried proving it for them? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$
    – D.W.
    Commented Oct 25, 2022 at 21:18
  • $\begingroup$ If you are unsure how to prove mapping reducibility between two specific languages, before attempting this exercise, I suggest that you study mapping reducibility and read some examples of such reductions. Any good textbook on this topic should have coverage of that. $\endgroup$
    – D.W.
    Commented Oct 25, 2022 at 21:19

1 Answer 1

1
$\begingroup$

You won't be able to prove this, because it is false. Let $J$ be an arbtirary undecidable language. Let $L = \{2n \mid n \in J\} \cup \{2n+1 \mid n \notin J\}$. Then $L$ is undecidable, and $L \equiv_m L^c$ via the map $2n \mapsto 2n+1, 2n+1 \mapsto 2n$.

What is true is there are some undecidable languages which are not many-one reducible to their complements. The usual example here is showing that the complement of the Halting problem not many-one reducing to the Halting problem, taking into consideration that being computably enumerable is downwards closed under many-one reductions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.