The Halting Problem

Is it possible to write a program A that takes another program B as input and which determines if B will halt or loop forever?

Well it turns out that an assumption that the answer is “yes” leads to a paradox and hence there is a proof by contradiction that the correct answer must be “no”.

The proof goes like this:

Assume program A can determine if program B will halt or loop forever.

Now I write a program C that calls program A as follows:

B = input_program
if A says B will halt then
   loop forever
else
   stop
end if

And I now feed program C to itself as input.

The result is that if C will halt, then it will loop forever, but if it will loop forever, then it will halt.