Problem:
Let $ A $ be a Turing-recognizable language consisting of descriptions of Turing machines, $ \{(M_1 ), (M_2), \cdots \}$, 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 $.)
Short answer:
We can adopt the diagonalization argument to produce a decidable language that is not accepted by any of the $ M_i $.
Proof:
Consider the language $ D $ decided by the following Turing machine
Reject any input that is not a binary number.
Enumerate the ith Turing machine, where $ i $ is the input string.
If $ M_i $ accept the input string, reject it, otherwise accept it.
Apparently this is a Turing machine, and it is not accepted by any of the $ M_i $ (there is always a string $ i $ where $ M_i $ does not agree with $ D $)
Let $ A $ be a Turing-recognizable language consisting of descriptions of Turing machines, $ \{(M_1 ), (M_2), \cdots \}$, 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 $.)
Short answer:
We can adopt the diagonalization argument to produce a decidable language that is not accepted by any of the $ M_i $.
Proof:
Consider the language $ D $ decided by the following Turing machine
Reject any input that is not a binary number.
Enumerate the ith Turing machine, where $ i $ is the input string.
If $ M_i $ accept the input string, reject it, otherwise accept it.
Apparently this is a Turing machine, and it is not accepted by any of the $ M_i $ (there is always a string $ i $ where $ M_i $ does not agree with $ D $)
No comments :
Post a Comment