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.