Let's show that $A_{\mathsf{TM}}$, or membership for Turing machines, is undecidable.
$A_{\mathsf{TM}}$ is undecidable.
We assume that $A_{\mathsf{TM}}$ is decidable and end up showing that it isn't. Suppose we have a TM $H$ that decides $A_{\mathsf{TM}}$. Then on $\llbracket M,w \rrbracket$, $H$ halts and accepts if $M$ accepts $w$ and it rejects if $M$ does not accept $w$.
We construct a new TM $D$ that takes as input the description of a Turing machine and operates as follows:
Let's consider the result of running each Turing machine on a string of encodings of Turing machines. Essentially, we have \[L(D) = \{\llbracket M \rrbracket \in \Sigma^* \mid \llbracket M \rrbracket \not \in L(M)\}.\]
Again, we can view this as a table. Suppose we have an enumeration of Turing machines $M_1, M_2, \dots$. Then, we have the list of Turing machine encodings running down and whether the $i$th machine accepts it running across. Now, let's consider the result of $D$ when run on a description of one of these machines: it is basically the opposite of whatever runs along the diagonal.
| $M_1$ | $M_2$ | $M_3$ | $M_4$ | $M_5$ | $\cdots$ | $D$ | $\cdots$ | |
| $\llbracket M_1 \rrbracket$ | ✔️️ | ❌ | ✔️️ | ✔️️ | ❌ | ❌ | ||
| $\llbracket M_2 \rrbracket$ | ✔️️ | ❌ | ✔️️ | ❌ | ❌ | ✔️️ | ||
| $\llbracket M_3 \rrbracket$ | ❌ | ✔️️ | ✔️️ | ✔️️ | ❌ | ❌ | ||
| $\llbracket M_4 \rrbracket$ | ✔️️ | ❌ | ❌ | ❌ | ❌ | ✔️️ | ||
| $\llbracket M_5 \rrbracket$ | ✔️️ | ❌ | ✔️️ | ✔️️ | ❌ | ✔️️ | ||
| $\vdots$ | $\ddots$ | $\vdots$ | ||||||
| $\llbracket D \rrbracket$ | ❌ | ✔️️ | ✔️️ | ❌ | ✔️️ | $\cdots$ | ⁇ | $\cdots$ |
| $\vdots$ | $\vdots$ | $\ddots$ |
Now, let us consider the result of $D$ when run on the input string $\llbracket D \rrbracket$. We have \[\llbracket D \rrbracket \in L(D) \iff \llbracket D \rrbracket \not \in L(D).\] That is, $D$ must accept if $D$ does not accept $\llbracket D \rrbracket$ and it must reject if $D$ accepts $\llbracket D \rrbracket$, which is a contradiction. Thus, neither Turing machines $D$ or $H$ can exist and $A_{\mathsf{TM}}$ is undecidable.
This result will be quite handy. We can make use of this to show that there are many other problems that aren't decidable either. To start, we'll consider a problem that you've likely already heard about: Turing's halting problem. The halting problem is defined \[ \mathsf{HALT}_{\mathsf{TM}} = \{ \llbracket M,w \rrbracket \mid \text{$M$ is a TM and $M$ halts on input $w$} \}.\]
$\mathsf{HALT}_{\mathsf{TM}}$ is undecidable.
Assume that there exists a Turing machine $H$ that decides $\mathsf{HALT}_{\mathsf{TM}}$. Then we can construct the following Turing machine to decide $A_{\mathsf{TM}}$:
So if $H$ decides $\mathsf{HALT}_{\mathsf{TM}}$, then we can decide $A_{\mathsf{TM}}$ with the preceding TM. However, we know that $A_{\mathsf{TM}}$ is undecidable, so this is a contradiction and $\mathsf{HALT}_{\mathsf{TM}}$ must be undecidable.
As it turns out, Turing's original proof of (what we now call) the halting problem is shown directly via a diagonal argument like the proof of the undecidability of $A_{\mathsf{TM}}$. It's not too hard to see how we might be able to modify the proof of $A_{\mathsf{TM}}$ to work for the halting problem.
Why is this problem of interest? In modern terms, this is the problem of determining whether a given program ever halts on a particular input. You can think of this as being able to check for infinite loops without actually running the program and only by examining the source code of the program.
But originally, this was already quite interesting mathematically. Consider a problem like Goldbach's conjecture: Every even natural number greater than 2 is the sum of two prime numbers. We can write a short program that tests every even number and stops after it finds one that isn't the sum of two primes. Does the program ever halt? If it does, then this disproves the conjecture.
And recall that the original context of this work was in trying to determine whether mathematics was decidable in this way. And in order to know this, any such algorithm would have to be guaranteed to stop and produce an answer.
Let's look at some more examples of undecidable languages. To show that these languages are undecidable, we will start using an idea that is fairly central to theoretical computer science: reducibility. If you've taken algorithms or complexity theory, this is the same idea behind reductions in those courses.
Essentially, this is the idea that you can be clever about using a solution to some other problem you've already solved. For instance, it is a bit tedious to show that a problem is undecidable by setting up a diagonalization argument every time. Instead, we can make use of results that we've already proved, which in this case would involve reducing a problem to some other problem that we know is already undecidable.
In fact, we already did this to show that the Halting problem was undecidable: instead of constructing a bespoke diagonalization proof, we made use of the fact that we already showed $A_{\mathsf{TM}}$ was undecidable. Schematically, this looks kind of like the following:
Here's the idea. Suppose we want to show that some language $L$ is undecidable. Let's assume it's decidable—then there's a Turing machine we can run that will decide it. We can then use this Turing machine to decide something we've already shown is undecidable. This can't be right—it's a contradiction, so our assumption that our language was undecidable must have been incorrect.
Let's consider the emptiness problem for Turing machines. That is, given a Turing machine, does it not accept anything? This is the language \[ E_{\mathsf{TM}} = \{ \llbracket M \rrbracket \mid \text{$M$ is a TM and $L(M) = \emptyset$} \}. \]
$E_{\mathsf{TM}}$ is undecidable.
In modern terms, we might think of this as trying to see if a given program produces anything at all.
First, we describe the construction for a machine $M_w$ that is based on some Turing machine $M$ and some string $w$. It operates in the following way:
The machine $M_w$ rejects every word that is not $w$. Then the only word that can be accepted is $w$. If $M_w$ doesn't accept $w$, then $L(M_w) = \emptyset$. In other words, we can describe the language of $M_w$ as \[L(M_w) = \begin{cases} \{w\} & \text{if $M$ accepts $w$}, \\ \emptyset & \text{if $M$ does not accept $w$}. \end{cases}\] Thus, $M_w$ recognizes the empty language if and only if it doesn't accept $w$. We will use this construction in our proof.
Now, we assume that there exists a TM $R$ that decides $E_{\mathsf{TM}}$ and construct a TM $S$ that decides $A_{\mathsf{TM}}$ as follows:
Thus, if $R$ decides $E_{\mathsf{TM}}$, then $S$ decides $A_{\mathsf{TM}}$. However, we know that $A_{\mathsf{TM}}$ is undecidable, so $R$ cannot exist and $E_{\mathsf{TM}}$ is undecidable.
This gives us a handy way to show that other decision problems for Turing machines are undecidable. Let's consider the problem of equality between two TMs, specified as \[\mathsf{EQ}_{\mathsf{TM}} = \{ \llbracket M_1, M_2 \rrbracket \mid \text{$M_1,M_2$ are TMs and $L(M_1) = L(M_2)$} \}.\]
$\mathsf{EQ}_{\mathsf{TM}}$ is undecidable.
This time, we reduce from $E_{\mathsf{TM}}$. Suppose we have a TM $R$ that decides $\mathsf{EQ}_{\mathsf{TM}}$. Then we can construct the following TM to decide $E_{\mathsf{TM}}$.
Here, $N$ rejects all input so $L(N) = \emptyset$. If we test whether $M$ and $N$ accept the same language, then we're basically testing whether $L(M) = \emptyset$ and now we have a way to decide $E_{\mathsf{TM}}$.