Problem Detail: An exercise that was in a past session is the following:
Prove that there exists an undecidable subset of ${1}^*$
This exercise looks very strange to me, because I think that all subsets are decidable. Is there a topic that I should read to find a possible answer?
Asked By : Vitalij Zadneprovskij
Answered By : Hendrik Jan
Note that ${1}^*$ is isomorphic to $Bbb N$. There are uncountably many subsets of both ${1}^*$ and $Bbb N$. Perhaps you are confused with the fact that there are only countably many finite subsets of ${1}^*$ (and $Bbb N$).
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/19329
