The "you can embed the program in itself" is, as far as I know, the main reason why a true proof of this is rather complicated, there's a bit of technicality involved in order to be able to show that.
The 'halting' part confused me initially. It always came along with Turing machine explanations...
But, the paradox extands beyond 'halting.'
I think.
You could just as well say, "There can be no program that can determine, in all cases, if a program prints, 'HELLO WORLD'"
Right?
The function(x) would be true if x produces "HELLO WORD" and false otherwise, where 'x' is the program itself. Then... if (f(x)){print "Goodbye World")... etc., etc.
If you're interested, this book explains the halting problem, Rice's theorem and much more in a rather accessible and intuitive manner without using too much formal mathematics (it uses Ruby instead): https://computationbook.com/
But, the paradox extands beyond 'halting.'
I think.
You could just as well say, "There can be no program that can determine, in all cases, if a program prints, 'HELLO WORLD'"
Right?
The function(x) would be true if x produces "HELLO WORD" and false otherwise, where 'x' is the program itself. Then... if (f(x)){print "Goodbye World")... etc., etc.