World's most popular travel blog for travel bloggers.

[Solved]: how do I find a undecidable subset of a set that's decidable?

, , No Comments
Problem Detail: 

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?

Asked By : user3277633

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22839

0 comments:

Post a Comment

Let us know your responses and feedback