Undecidable unary languages (also known as Tally languages)

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