News for hackers. Stuff that matters.
Re:Weakening Cycles So That Turing Can Halt by cortesoft on Thursday May 14, 2020 @09:03PM (#23187688)
If it definitely exists, don't we then know that this program will definitely halt?
Re:Weakening Cycles So That Turing Can Halt by garganzol on Thursday May 14, 2020 @09:22PM (#23187792)
Only from algebraic and philosophical standpoints. This knowledge is not 100% precise unless a specific number is found.
Re:Weakening Cycles So That Turing Can Halt by groby_b on Thursday May 14, 2020 @09:42PM (#23187913)
Nobody cares about the halting problem from a specific standpoint. If it's algebraically guaranteed to halt, it halts. When it halts is entirely meaningless for purposes of the halting problem.

But the thing is, it isn't algebraically guaranteed either - we still don't know if an odd perfect number exists. (I'm not sure where the "Definitely. Somewhere in 10^300 range." is coming from. There's nothing definite about the existence, only constraints that need to be satisfied if it exists)

Re:Weakening Cycles So That Turing Can Halt by ProblemFactory on Friday May 15, 2020 @07:19AM (#23190869)
> Nobody cares about the halting problem from a specific standpoint. If it's algebraically guaranteed to halt, it halts. When it halts is entirely meaningless for purposes of the halting problem.

Halting problem from a specific standpoint is a popular area of research. Microsoft Research in particular has been active in this area, and Windows device drivers and other kernel event handlers are analyzed to prove that they will halt in a reasonable amount of time to avoid locking up the OS.

https://www.microsoft.com/en-us/research/publication/t2-temp...

Re:Weakening Cycles So That Turing Can Halt by cortesoft on Thursday May 14, 2020 @09:45PM (#23187937)
In fairness, though, the halting problem doesn't care if you can predict if SOME programs halt... you have to predict if ALL programs halt.
Re:Weakening Cycles So That Turing Can Halt by groby_b on Thursday May 14, 2020 @09:49PM (#23187965)
There's that, too. (Well, we don't have to predict anything. We have to show that halting or not is a decidable condition, and we've shown it isn't. Even if we had shown it was decidable, there still might be programs where we practically can't figure out it halts. So is the beauty of math - it gives us the gestalt of the world without caring about the world :)
Re:Weakening Cycles So That Turing Can Halt by greydius on Thursday May 14, 2020 @10:52PM (#23188330)
If you've prove a finite upper bound,then you've proven the program will halt. You don't need to know what the exact number is.
Re:Weakening Cycles So That Turing Can Halt by garganzol on Saturday May 16, 2020 @08:58PM (#23208478)
The trick with boundaries does not stand true for evasive predicates on unbounded data.

Please note that suggested odd perfect number search algorithm in Python uses an evasive predicate on a big integer which is unbounded.

This means that a typical tracer (or verifier in Turing terms) won't be able to infer the upper bound for the given example.