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?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ This is a dump of a homework problem. It has also been previously asked on this site. $\endgroup$– Yuval FilmusMar 20, 2014 at 1:57
-
$\begingroup$ Any set (even undecidable ones) are subsets of the set of all strings... $\endgroup$– vonbrandMar 21, 2014 at 0:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
Hint: For every language $L$, the language $M = \{ 1^{2x+1} : x \in L \}$ is a subset of $S$.
answered Mar 20, 2014 at 1:59
-
$\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