3 ms·

> The halting problem tells us that it’s plausible that that instinct is right - that for some programs, you really can’t do some other analysis of the program

> The halting problem tells us that it’s plausible that that instinct is right - that for some programs, you really can’t do some other analysis of the program that tells you what it’s going to do. You have to just run it. 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.

ttctciyf 3y ago
> 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.
- amelius 3y ago
  But that is not the only possibility. So you are missing the point.
  - Sinidir 3y ago
    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.
    - amelius 3y ago
      Besides missing the point, this is also pedantic and quite boring.
- SideQuark 3y ago
  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.
  - ttctciyf 3y ago
    > Only if you've waited long enough, which can be arbitrarily far out, and it stops, can you answer So, we agree!
simiones 3y ago
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.

ttctciyf 3y ago

> 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.

amelius 3y ago
But that is not the only possibility. So you are missing the point.
- Sinidir 3y ago
  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.
  - amelius 3y ago
    Besides missing the point, this is also pedantic and quite boring.
SideQuark 3y ago
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.
- ttctciyf 3y ago
  > Only if you've waited long enough, which can be arbitrarily far out, and it stops, can you answer So, we agree!

simiones 3y ago

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.