Are the implications of the diagonalization language different from those of the halting problem? [duplicate]

Question

This question already has an answer here:

• Why, really, is the Halting Problem so important? 11 answers

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.

Answer 1

I think that "limits of computation" is a good entry point. Usually, computer scientists learn how to solve problems in an logical and algorithmic way. The whole concept of undecidability is to show that there are problems which cannot be solved in this way, which may sounds surprising but also exciting, that there is an actual limit to what is possible with computers (even with infinite memory).

You actually do not need the diagonalization language to show that there are undecidable problems as this follows already from a combinatorical argument: You can enumerate the set of all Turing machines (sometimes called Gödelization). Thus, you have only countable many decidable languages. But the set $2^{\{0, 1\}^\ast}$, i.e. the set of all languages over $\{0, 1\}$, is uncountable, so there have to be undecidable languages.

The diagonalization language (I assume $D = \{\langle M \rangle \mid M \text{ halts on } \langle M \rangle\}$ is by all means very constructed but the proof that this language is undecidable is a good stating point because the proof via diagonalization is easy and the usual variations of the halting problems are not really far away. The next steps are probably Turing reductions from this language to some of these variations.