4 ms·
That’s a very good explanation. When I first read about it years ago, I mistakenly assumed it was ‘deeper’ or more profound. But, at the end of the day, it is
by lurquer 5y ago
That’s a very good explanation.
When I first read about it years ago, I mistakenly assumed it was ‘deeper’ or more profound.
But, at the end of the day, it is just a variant in the old “This Sentence Is False” riddle you’d encounter as a kid.
Papers on the topic are frequently spruced up with complicated gibberish... but, unless we are both missing something fundamental, it’s really as simple as set forth in your post.
- Tainnor 5y agoThe "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.
- lurquer 5y agoThe '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.
- Tainnor 5y agoYes, this is Rice's theorem: https://en.wikipedia.org/wiki/Rice%27s_theorem https://en.wikipedia.org/wiki/Rice%27s_theorem 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/ https://computationbook.com/