2
$\begingroup$

Consider strings $s \in \{0,1\}^*$. Define $c_1(s)$ to be the ones' complement of $s$; i.e., the string obtained from $s$ by inverting all of its bits. So, for example, $c_1(000111) = 111000$. Call a language $L \subset \{0,1\}^*$ ones' complement closed, or OCC, if $s' \in L$ $\iff$ $c_1(s') \in L$, provided $s'$ is not the empty string. Given these assumptions, I have a few questions.

Does there exist an OCC language that is both Turing-recognizable and not decidable?

Does there exist an OCC language $L$ with the property that both $L$ is not decidable and $\overline{L}$ is Turing-recognizable?

Does there exist an OCC language $L$ that is such that neither it nor $\overline{L}$ is Turing-recognizable?

I am having some trouble answering these questions because of how limited the alphabet $\{0,1\}$ is. I was thinking that perhaps this alphabet alone could be used to encode Turing machines, and from there we could talk about the well-known decidable/undecidable and recognizable/not-recognizable languages involving Turing machine encodings, but I'm not sure this is possible.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
2
$\begingroup$

Given a language $L$, you can create a language $L'$ which is equivalent in power and OCC: $$ L' = \{ 0 x : x \in L \} \cup \{ 1 c_1(x) : x \in L \}. $$ The two languages are recursively equivalent. This means that there is a computable reduction from $L$ to $L'$ and another one from $L'$ to $L$.

Using this construction, you can now answer your own question.

Improve this answer
$\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.