online advertising

Wednesday, January 4, 2017

A Turing-recognizable language consisting of descriptions of Turing machines

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 $)

No comments :

Post a Comment