# Michael Sipser Edition 3 Exercise 5 Question 23 (Page No. 240)

32 views
Show that $A$ is decidable iff $A \leq_{m} 0 ^{\ast} 1^{\ast}$ .

## Related questions

1
36 views
Give an example of an undecidable language $B$, where $B \leq_{m} \overline{B}$.
Let $AMBIG_{CFG} = \{\langle G \rangle \mid \text{G is an ambiguous CFG}\}$. Show that $AMBIG_{CFG}$ is undecidable. (Hint: Use a reduction from $PCP$ ... $a_{1},\dots,a_{k}$ are new terminal symbols. Prove that this reduction works.)
Show that if $A$ is Turing-recognizable and $A\leq_{m} \overline{A},$ then $A$ is decidable.
Show that $A$ is Turing-recognizable iff $A \leq_{m} A_{TM}$.