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.