2

Hello my dear friends!
I have following problem: Prove that exists undecidable subset of $\{1\}*$
The problem is that I don't know how to start. In real I don't what does it mean undecidable set ?

1 Answers1

3

for the definition of decidability/undecidability checkout these set of slides.

To prove the above claim, notice that we can set up a mapping from $\{0,1\}$* to $\{1\}$* by mapping any $ x \in \{0,1\}$* to $1^{1\operatorname{bin}x}$

Also we know the fact that any of the well known undecidable languages such as $A_{TM} = \{<M, w> | M \space \text{accepts} \space w\}$ can be encoded using binary. So we clearly has a subset over $\{0,1\}$* which is undecidable and we also established a mapping from $\{0,1\}$* to $\{1\}$* and hence the same undecidable language can now also be encoded in $\{1\}$* using the above scheme giving the undecidable language in $\{1\}$*.

John Bentin
  • 18,454
udion
  • 31
  • the earlier version looked better, the * is suppose to be in the superscript as it was before – udion Apr 15 '18 at 14:56