Examples of undecidable languages contained in 1*?

Question

I've been given the following question

Show that there is an undecidable language contained in $1^*$.

But I can't think of any undecidable languages that are contained! Can someone please lend a helping hand, if only a hint!

Answer 1

How about using the halting set? $$ L = \{ 1^k \mid k = <i,j> \wedge \, (i,j) \in H \}, \quad H = \{ (i,j) \mid \varphi_i(j) \ne \mbox{div} \} $$ where $\varphi_i$ is the $i$-th computable function (Gödel numbering) and $\mbox{div}$ is the assigned value, if the function does not terminate.

$<i,j>$ is the encoding of two natural numbers into into one number, e.g. using the Cantor pairing function $\pi : \mathbb{N}\times\mathbb{N} \to \mathbb{N}$, $<i,j> = \pi(i,j)$.

So if the $42$-th computable function terminates on input $123$, we would have some result $\phi_{42}(123) \in \mathbb{N}$ and thus $(42,123) \in H$. We encode $42$ and $123$ into $<42,123> = 4$ (or whatever value :) and thus $L$ would contain $1^4 = 1111$.

Or: $\Psi : \mathbb{N}^2 \to 1^*, (i,j) \mapsto 1^{\pi(i,j)}$ maps $H$ bijectively to $L$, $L = \Psi(H)$.

The halting problem is undecidable, so is $H$, so should be $L \subseteq 1^*$.

Answer 2

Hint. I doubt, one can explicitly give one language, but there are many: Note that there are only countably many decidable languages (as there are only countably many Turiung machines). But: $1^* = \{1^n \mid n \in \mathbf N\}$ has uncountably many subsets.