Given that Let S = {a | |a| is odd}. I know that since S is decidable, but does there exist a subset within S that is undecidable?

  • 1
    $\begingroup$ This is a dump of a homework problem. It has also been previously asked on this site. $\endgroup$ Mar 20, 2014 at 1:57
  • $\begingroup$ Any set (even undecidable ones) are subsets of the set of all strings... $\endgroup$
    – vonbrand
    Mar 21, 2014 at 0:04

1 Answer 1


Hint: For every language $L$, the language $M = \{ 1^{2x+1} : x \in L \}$ is a subset of $S$.

  • $\begingroup$ thanks for the hint. If L contains all natural numbers, wouldn't M = {1} since 1 to any power will remain 1, and even though M is a subset of S, M only contains 1 and is decidable? $\endgroup$ Mar 20, 2014 at 2:04
  • $\begingroup$ Here $1^{2x+1}$ is the string of length $2x+1$ consisting only of $1$s. $\endgroup$ Mar 20, 2014 at 2:05
  • $\begingroup$ I am confused as to why a language with only odd number of 1s would be a subset of S. Am I misinterpreting the question by thinking that x must be a number? $\endgroup$ Mar 20, 2014 at 2:11
  • $\begingroup$ Well, $S$ consists of all strings of odd length... $\endgroup$ Mar 20, 2014 at 2:15

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