Proof of the undecidability of the Halting Problem

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?


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 MM(P)= does P not accept P?

The contradiction happens when you ask: does M accept M? Try to work out the two options to see how there is a contradiction.

M accepts M if and only if M does not accept M; 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.

Source : Link , Question Author : Netik , Answer Author : psmears

Leave a Comment