Re:Weakening Cycles So That Turing Can Halt
by saagarjha on Thursday May 14, 2020 @10:44PM
(#23188289)
Well, 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.
Re:Weakening Cycles So That Turing Can Halt
by whatshisface on Friday May 15, 2020 @12:44AM
(#23188979)
In 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.
If 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.
If it doesn't take 100 years to complete, it doesn't take 100 years to complete.
Take 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.
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.