3 ms·
Paradoxical self-reference cycles seem to give rise to the halting problem, the incompleteness theorem, the liar paradox, and Russell's paradox (among other par
by musicale 7y ago
Paradoxical self-reference cycles seem to give rise to the halting problem, the incompleteness theorem, the liar paradox, and Russell's paradox (among other paradoxes and self-contradictions) so breaking those cycles seems like a practical idea.
However, in practice there really isn't a noticeable difference between a program that never completes and one that takes 100 years to complete. Both programs will almost certainly be halted (or at least paused indefinitely) by some external means. If a program takes too long to produce its desired output, then it simply isn't a useful piece of software.
- saagarjha 7y agoWell, that depends. A program that takes 100 years to complete (say factoring a large number) can be optimized to not take 100 years, and it is worth looking for algorithmic advances that would make that possible. A program that can proven to never halt (a soundness detector that checks programs for behavioral violations) can never be perfect and must rely on heuristics or be known to fail on certain input.
- whatshisface 7y agoIn fact, 100 years to 1/10th of a year is a mere constant factor, that could be arrived at in some cases by buying a lot of GPUs.
- musicale 7y agoIf it doesn't take 100 years to complete, then it doesn't take 100 years to complete. But it is a sort of good point that a 100 year runtime in 2020 might turn into a 10 year runtime in 2030, making it only a 20 year runtime overall. For some jobs, a 20 year runtime might be acceptable, but probably those jobs are rare. In general if a program takes so long to complete that its output is no longer useful, that limits its practicality and utility.
- musicale 7y agoIf it doesn't take 100 years to complete, it doesn't take 100 years to complete.
- yters 7y agoTake an algorithm that halts soon enough. Now scan a bunch of them to find the good enough one. This new scanning process no longer halts soon enough. Even with runtime limits the halting problem is annoying.