2 ms·
The 'halting' part confused me initially. It always came along with Turing machine explanations... But, the paradox extands beyond 'halting.' I think. You co
by lurquer 5y ago
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.
- 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/