Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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$).
A related question on StackOverflow is this one. Also the answer by Haile to this one is there:
Since the universe of strings over any finite alphabet is countable, every language can be mapped to a subset of the natural numbers. So you just have to take a Recursively enumerable language wich is not decidable and map it into a subset of $\{1\}^*$.
For example, in the classic version of the halting problem we enumerate every turing machine into a binary string; you can now sort all the turing machines and define a map $f : TM \rightarrow N$ from Turing machines to integers where $f(TM) = n$ if TM is the nth Turing Machine in the ordered list of all TM.
Now, the halting problem for Turing Machines coded as unary numbers is r.e. but not decidable.
Another related question in this one.
