Proving that the set of deciders is not Turing-recognizable

Question

Let $A$ be the language consisting of descriptions of Turing machines $\{M_1, M_2, \dots \}$, where each $M_i$ is a decider. Prove that $A$ is not Turing-recognizable.

Then suppose $A$ is Turing-recognizable and suppose $s = \{s_1, s_2, \dots \}$ is a set of all possible binary strings. Then I construct decider $D$ as follows. On input $w$, if $w$ is not equal to binary string, then reject. Else, $w$ is a binary string that is equal to $s_i$ for some $i$. Use the enumerator $E$ to print the $i$-th output which is $M_i$. If $M_i$ accepts $s_i$, $D$ is going to reject $s_i$. Otherwise, accept $s_i$.

But in the last step, what happens when $M_i$ doesn't have defined transition over the alphabet $\{0,1\}$? Does $M_i$ immediately enter a reject state? What should I argue?

Answer 1

The basic idea of the proof is to come up with a Turing machine which doesn't belong to the enumeration, hence contradicting the claim that deciders can be enumerated. To this end, we use diagonalization – for each potential machine in the enumerate, we ensure that there is at least one input on which the diagonalizing machine has a different behavior.

If the diagonalizing machine $D$ has alphabet $\Sigma$, then we already know that any machine in the enumeration with a different alphabet cannot be $D$. Therefore $D$ doesn't care much about these machines. What $D$ has to ensure is that for every machine $M_i$ with alphabet $\Sigma$ there is an input $x_i$ such that $D(x_i) \neq M_i(x_i)$.