Re:The Halting Problem Is Decidable on a Set of Asymptotic P...
by ttctciyf on Sunday May 28, 2023 @04:27PM
(#36107451)
> If you just run it, you will not learn whether or not it halts after any finite amount of time.
If it halts within a finite amount of time, you will.
Re:The Halting Problem Is Decidable on a Set of Asymptotic P...
by amelius on Sunday May 28, 2023 @06:31PM
(#36108416)
But that is not the only possibility. So you are missing the point.
Re:The Halting Problem Is Decidable on a Set of Asymptotic P...
by Sinidir on Sunday May 28, 2023 @07:45PM
(#36108932)
They are not missing the point. The previous post was simply wrong. The halting problem is semi-decidable. So you can potentially find out wether a program halts.
Re:The Halting Problem Is Decidable on a Set of Asymptotic P...
by amelius on Sunday May 28, 2023 @07:58PM
(#36109020)
Besides missing the point, this is also pedantic and quite boring.
Re:The Halting Problem Is Decidable on a Set of Asymptotic P...
by SideQuark on Sunday May 28, 2023 @10:19PM
(#36109871)
No you won't. Pick any finite time you will check. It may not stop by then, yet may stop later. So ahead of time, even if the program will stop, you cannot make a plan to learn that in finite time. You're stuck letting run possibly forever, because at each finite time you still cannot answer yes or no. Only if you've waited long enough, which can be arbitrarily far out, and it stops, can you answer.
Re:The Halting Problem Is Decidable on a Set of Asymptotic P...
by ttctciyf on Monday May 29, 2023 @01:44AM
(#36111052)
> Only if you've waited long enough, which can be arbitrarily far out, and it stops, can you answer
So, we agree!
Re:The Halting Problem Is Decidable on a Set of Asymptotic P...
by simiones on Monday May 29, 2023 @05:44AM
(#36112331)
Well, it depends how you take it. The fact that the halting problem is undecidable tells us that there is no algorithm to tell if an algorithm will ever halt for some input. This implies that the best we can do if we want to find out if an arbitrary algorithm A will halt for some input B is to run A with input B. We may still never find out, but we also have no better way.
This isn't quite right. The halting problem says that you can't just run it. If you just run it, you will not learn whether or not it halts after any finite amount of time.
Also I don't see how this is related to uncertainty bounds.