This question already has an answer here:
Revised: In my previous question, I was confused about the implications of the diagonalization language. I concluded that it proves there are languages for which there are no recognizable turing machine. However, how is this implication different from the halting problem? Do they both just reinforce the limitations of computability?
Old post:
I'm in an introductory computer theory course. The professor went over the diagonalization argument and showed how the diagonalization language is not decidable.
The diagonalization language is the set of all pairs of turing machines and strings that they accept. In other words, $L = \{ (s_i, M_i) | M_i$ accepts $s_i \}$. We can encode each turing machine as a binary string and sort them in lexographic order. We can then fix an alphabet $\Sigma$ and then put $\Sigma^*$ in lexographic order. By creating a table with these lists, where the values in the table are either 1 for accept or 0 for reject, we define a language to be any diagonal row in the table. Now we consider the complement of the diagonal language, which takes the complement of each value in the main diagonal. We quickly see that there is no turing machine that recognizes this language - as we switch every accept value to reject. Thus we have proved that exist languages for which there is no recognizing turing machine.
In class the professor actually said that this argument proves undecidability.
I don't see the more general implications of this argument. For the purposes of a intro course on CS theory, what are the implications of the existence of undecidable languages on our understanding of turing machines? Do they mention it to show that there are limits to what is computable (but isn't that the purpose of the halting problem)?
I'm truly trying to understand why this proof is used in every textbook, because I don't grasp how it connects to the other sections about turing machines.