Question

Let A be a Turing-recognizable language consisting of descriptions of Turing machines, $\left\{\left(M_1\right),\left(M_2\right),...\right\}$, where everyM_iis a decider. Prove that some decidable languageDis not decided by any deciderM_iwhose description appears in A. (Hint: You may find it helpful to consider an enumerator for A.)

Short answer

The decidable language D is given that is not decided by any decider M_i

Step-by-step solution

Explain Turing machine

A Turing machine uses mathematics to simulate a machine that runs on tape mechanically. Such a machine is able to read and write symbols on a tape one at a time using a tape head. A limited number of simple instructions decide the operation completely.

Prove that D is not decidable

There is an enumerator E that counts A since it is Turing-recognizable. Allow M_i to be the i^th output of E. Let all the possible strings be $s1,s2,s3,\dots$and so on. Construct a Turing Machine D as described below.

Reject if w does not belong to $\left\{0,1\right\}*$.Otherwise, for some particular i, w is equal to s_i. Then, use E to numerate till M_i. After that, run M_i on w. Reject if M_i accepts. Otherwise, accept.

Thus, D is different fromany deciderM_i and not in A.