For any string $s \in \{0,1\}^*$, let the ones' complement of $s$, denoted $1_c(s)$, be the string obtained by flipping all bits in $s$. For example, $1_c(001100) = 110011$. Now call a language $L \subset \{0,1\}^*$ ones' complement asymmetric or OCA for short, if for every string $s \in \{0,1\}^+$, precisely one of $s$ and $1_c(s)$ is in $L$.

I want to come up with a mapping reduction from a language $L \subset \{0,1\}^*$ to an OCA language (and vice-versa) so as to prove the existence of decidable/recognizable and undecidable/co-recognizable and undecidable, etc., OCA languages. My problem is especially that we require every string in $\{0,1\}^+$ to be such that either it or its ones' complement appears in any OCA language. This seems particularly problematic if $L$ lacks strings of a particular length, meaning it isn't obvious how we'd go about constructing an OCA language from $L$.


1 Answer 1


I don't think there exist recognizable-but-undecidable OCA languages, because if we have a Turing machine M that recognizes a given OCA language, then we can create a derived Turing machine that incrementally simulates M on both its input and its one's-complement (flipping back and forth, trying a finite number of steps in each simulation) until one input or the other has been recognized.

(Note: the derived Turing machine will also need to be given specific logic to decide the empty string; but that's obviously possible to do for any given language.)

Therefore, you can't construct any reduction mapping that would let you prove the existence of recognizable-but-undecidable OCA languages.


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.