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 ?
Asked
Active
Viewed 5,130 times
2
user220688
- 509
1 Answers
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