# What is the role of diagonalization in the proof of undecidability of the halting problem?

I'm trying to understand the proof of undecidability of the halting problem. Some resources give a short proof based on a proof by contradiction. There is no mention of diagonalization. But some others also mention diagonalization in the proof. I'm rather confused about the role of diagonalization in this proof. Is it needed? If yes what is its role? Or can the proof be done without utilizing diagonalization?

• Yes, the proof you pointed to is refutation by contradiction (it explicitly says "proof by contradiction" and proceeds to refute the claim by assuming it). It is a proof by diagonalization, specifically at one point is says "how about $\mathrm{OPP}(\mathrm{OPP})$?". This sort of self-application is a telltale sign that diagonalization is occuring. (P.S. I do not recommend this proof. There are classic textbooks that do a much better job, but nothing beats this video, which is also refutation by contradiction using diagonalization.) Mar 2 at 9:12
• The pures for of diagonalization appears in Lawvere's fixed point theorem, all the others are derivatives of this one. The "diagonalization" parts appears when a map $\phi : A \to B^A$ (see the link for details) is applied twice to the same argument, $\phi(p)(p)$. If you think about it, $\{(p,p) \mid p \in A\} \subseteq A \times A$ is the diagonal in the cartesian product $A \times A$, hence the name. Mar 2 at 15:29