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.
[ Parent
| on HN ]
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.