1
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

5
$\begingroup$

Unless you found an unusual proof, they're all refutations by contradiction (not "proofs by contradiction", although that is common parlance) and they all are qlso a form of diagonalization: to refute the claim, we assume there were a halting oracle, and derive a contradiction by diagonalizing against the oracle.

You might be getting too hung up with what books call these proofs, and whether they bother to mention words "contradiction" and "diagonalization". They should all be the same proof, if we discount minor details in presentation.

$\endgroup$
10
  • $\begingroup$ For the problem "are there any functions that are not primitive recursive" it turned out that the Big Ackermann function provides the solution - it grows faster than any primitive recursive function can. It is conceivable that there might be a concrete function where for some reason halting cannot be determined. For example if the complexity of determining that P halts with input N grows so fast with N that no program can handle it. $\endgroup$
    – gnasher729
    Feb 29 at 1:09
  • 1
    $\begingroup$ @SanyoMn: Alas, I cannot because you did not point to any specific proofs. Here is what I can do: you show me proofs of non-existence of the halting oracle, and I will explain why they are all the same proof, which takes the form of diagonalization. If you find a proof that is not, I owe you a beer (or a drink of your choice). $\endgroup$ Feb 29 at 21:36
  • 2
    $\begingroup$ 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.) $\endgroup$ Mar 2 at 9:12
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 2 at 15:29
  • 1
    $\begingroup$ Here's a description of Lawvere's diagonalization argument with category theory removed. $\endgroup$ Mar 2 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.