Suppose that $\Sigma = \{c_1, \dots, c_m\}$ is some finite alphabet and supposing $s \in \Sigma^*$, let $\mathcal{I}_j(s)$ denote the number of instances of character $c_j$ in $s$. Call a string $s$ odd-parity absent iff $|\{j : \mathcal{I}_j(s) = 0\}|$ is odd. That is, $s$ is odd-parity absent iff an odd number of characters from the alphabet are missing from $s$. Call a language $L \subseteq \Sigma^*$ odd-parity absent iff every string in $L$ is odd-parity absent.

I want to show whether or not the following proposition is true: if $L$ is odd-parity absent, then $L$ must be Turing decidable/recognizable.

At first, I was considering employing Rice's Theorem to show that the odd-parity absent language of Turing machine encodings is a non-trivial property and hence undecidable, but it seems conceivable that two equivalent Turing machine descriptions may be such that one is odd-parity absent and the other is not, and so this wouldn't be a valid property. Further, it seems we can always describe two equivalent Turing machines using two completely disjoint alphabets.

Also, I am not sure whether the proposition holds in the case of Turing recognizability.

  • 1
    $\begingroup$ How many languages are odd-parity absent? ​ ​ $\endgroup$ – user12859 Jan 26 '17 at 0:34
  • $\begingroup$ Infinitely many, because there are infinitely many odd-parity absent strings. $\endgroup$ – student894 Jan 26 '17 at 1:00
  • $\begingroup$ What kind of infinity? ​ ​ $\endgroup$ – user12859 Jan 26 '17 at 1:13
  • $\begingroup$ I was thinking that every single language could be odd-parity absent, since you could just add some extra characters to $\Sigma$ that don't actually appear in the target language, but I'm not sure. $\endgroup$ – student894 Jan 26 '17 at 1:16
  • $\begingroup$ How many subsets does an infinite set have? ​ ​ $\endgroup$ – user12859 Jan 26 '17 at 1:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.