# computability – Why there is no Turing Machine that accepts the Diagonal Language? In the following I assume that the matrix has an 1 in coordinates $$(i,j)$$ if $$M_i$$ accepts $$sigma_j$$ and a $$0$$ otherwise (swapping all 1s and 0s does not affect the argument).

Consider the language $$L = {sigma_i in Sigma^* : sigma_i notin L(M_i) }$$ that contains all the words $$sigma_i$$ such that the entry at coordinates $$(i,i)$$ of the matrix is $$1$$. I will first show that $$L$$ is not acceptable.

Suppose towards a contradiction that there is some Turing machine $$M^*$$ that accepts $$L$$.
Since the set of Turing machines is enumerable, and the rows of the matrix are associated with an enumeration of all Turing machines, there must be some integer $$i ge 1$$ such that $$M_i = M^*$$.

Then consider the word $$sigma_i$$ and suppose that the entry at coordinates $$(i,i)$$ is $$1$$.
From the way the matrix is constructed you know that $$M_i$$ accepts $$sigma_i$$. However, by the definition of $$L$$, you also know that $$sigma_i notin L$$. This implies that $$M^* = M_i$$ cannot accept $$sigma_i$$. This is a contradiction.

If the entry at coordinates $$(i,i)$$ is $$0$$, then $$M_i$$ does not accept $$sigma_i$$. However, $$sigma_i in L$$ implying that $$M^* = M_i$$ accepts $$sigma_i$$. Again, this is a contradiction.

Going back to your language $$L_d$$: if $$L_d$$ were acceptable then so would be $$L$$.
Suppose towards a contradiction that there is a Turing Machine $$M$$ that accepts $$L_d$$.
To accept $$L$$ proceed as follows:

• find the index $$i$$ such that $$sigma_i = x$$. This can be done by enumerating the words in $$Sigma^*$$.
• Simulate $$M$$ with input $$i$$.
• If $$M$$ with input $$i$$ halts and accepts, accept.

Since this is a contradiction, $$L_d$$ cannot be acceptable. 