0
$\begingroup$

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?

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

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

| cite | improve this answer | |
$\endgroup$
  • $\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$ – user3277633 Mar 20 '14 at 2:04
  • $\begingroup$ Here $1^{2x+1}$ is the string of length $2x+1$ consisting only of $1$s. $\endgroup$ – Yuval Filmus Mar 20 '14 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$ – user3277633 Mar 20 '14 at 2:11
  • $\begingroup$ Well, $S$ consists of all strings of odd length... $\endgroup$ – Yuval Filmus Mar 20 '14 at 2:15

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