Question

Prove that there exists an undecidable subset of ${\left\{1\right\}}^{*}$.

Short answer

It is proven that there is undecidable subset in the set of${\left\{1\right\}}^{*}$

Step-by-step solution

Introduction to Undecidability

A problem is undecidable if no Turing Machine exist which will halt in finite amount of time.

Proving 1*undecidable

There can exist many subset of ${\left\{1\right\}}^{*}$which are undecidable.

For this, let s_nbe a string of length (n-1) 1s, where can be any natural number.

So, we can identify any subset ‘s’ of ${\left\{1\right\}}^{*}$with infinite binary string. The j^thsymbol of the string will be 1 if and only if s_i is in subset s or 0 symbol otherwise.

It is clear that the mapping of each subset to its corresponding infinite binary string will be unique.

It is known that , number of subset in ${\left\{1\right\}}^{*}$will be equal to number of infinite binary string. Also there will be finite or countable number of Turing Machine. Thus, there must be certain subset of ${\left\{1\right\}}^{*}$that is not Turing recognizable i.e., there Turing Machine cannot exists.

And as we know that, non-recognizable subset is also undecidable. Therefore, there exists at least one undecidable subset of${\left\{1\right\}}^{*}$.