Register

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

• edited by
209 views
0 votes
0 votes
Let $J = \{w \mid \text{either $w = 0x$ for some $x \in A_{TM},$ or $w = 1y\:$ for some $y \in \overline{A_{TM}}\:\:$}\}$. Show that neither $J$ nor $\overline{J}$ is Turing-recognizable.
• edited by
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
2
admin asked Oct 17, 2019
137 views
Michael Sipser Edition 3 Exercise 4 Question 5 (Page No. 211)
Let $E_{TM} = \{\langle{ M \rangle } \mid M\: \text{is a TM}\: \text{and}\: L(M) = \phi\}$. Show that $E_{TM}$, the complement of $E_{TM}$, is Turing-recognizable.
Let $E_{TM} = \{\langle{ M \rangle } \mid M\: \text{is a TM}\: \text{and}\: L(M) = \phi\}$. Show that $E_{TM}$, the complement of $E_{TM}$, is Turing-recognizable.
User Avatar
0 votes
0 votes
0 answers
4
admin asked Oct 19, 2019
301 views
Michael Sipser Edition 3 Exercise 5 Question 25 (Page No. 240)
Give an example of an undecidable language $B$, where $B \leq_{m} \overline{B}$.
Give an example of an undecidable language $B$, where $B \leq_{m} \overline{B}$.
User Avatar
Link Copied!