# Michael Sipser Edition 3 Exercise 5 Question 7 (Page No. 239)

33 views
Show that if $A$ is Turing-recognizable and $A\leq_{m} \overline{A},$ then $A$ is decidable.

## Related questions

1
20 views
Show that $A$ is Turing-recognizable iff $A \leq_{m} A_{TM}$.
Say that a $CFG$ is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{CFG} = \{\langle G \rangle \mid \text{G is a minimal CFG}\}$. Show that $MIN_{CFG}$ is $T-$recognizable. Show that $MIN_{CFG}$ is undecidable.
Say that a variable $A$ in $CFG \:G$ is necessary if it appears in every derivation of some string $w \in G$. Let $NECESSARY_{CFG} = \{\langle G, A\rangle \mid \text{A is a necessary variable in G}\}$. Show that $NECESSARY_{CFG}$ is Turing-recognizable. Show that $NECESSARY_{CFG}$is undecidable.
Give an example of an undecidable language $B$, where $B \leq_{m} \overline{B}$.