312 views
0 votes
0 votes
Let $A$ be a Turing-recognizable language consisting of descriptions of Turing machines, $\{ \langle M_{1}\rangle,\langle M_{2}\rangle,\dots\}$, where every $M_{i}$ is a decider. Prove that some decidable language $D$ is not decided by any decider $M_{i}$ whose description appears in $A$. (Hint: You may find it helpful to consider an enumerator for $A$.)

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
1
0 votes
0 votes
0 answers
3