Proof of the undecidability of the Halting Problem

Problem Detail: 

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$?

Asked By : Netik

Answered By : aelguindy

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/65401