I'm having trouble understanding the proof of the undecidability of the Halting Problem.If $H(a,b)$ returns whether or not the program $a$ halts on input $b$, why do we have to pass the code of $P$ for both $a$ and $b$?Why can't we feed $H()$ with $P$ and some arbitrary input, say, $x$?
Proof of the undecidability of the Halting Problem
computability;turing machines
The proof aims to find a contradiction. You have to understand what the contradiction derived is, in order to understand why $P$ is used as an input to itself. The contradiction is, informally: if we have a machine H(a, b) that decides a accepts b, then we can construct a machine that accepts machines that do not accept themselves. (Read that a few times until you get it.) The machine shown in the picture – let's call it $M$ – $M(P) = $ does $P$ not accept $\langle P \rangle$?The contradiction happens when you ask: does $M$ accept $\langle M \rangle$? Try to work out the two options to see how there is a contradiction.$M$ accepts $\langle M \rangle$ if and only if $M$ does not accept $\langle M \rangle$; this is clearly a contradiction.This is why it is essential for the proof to run $P$ on itself not some arbitrary input. This is a common theme in impossibility proofs known as diagonal arguments.