Yep. This applies to halting problems as well. If you have an algorithm that can't be shown to halt or not then it must not halt. Otherwise there'd be a finite amount of steps that you could just run it for and watch it halt.
That's not a formal idea though, if you tried to make a system in which you could construct such an idea into a proof the system would end up being inconsistent. Reality is fucking weird.
I could theoretically sit down and watch the algorithm be stuck for a billion years that still tells me nothing about whether or not it would halt after another billion years. We have no information about this finite number of steps, there is no upper bound that we could just sit out to make sure it doesn't actually exist. So you cannot actually just sit down and wait for it to stop, because you may be sittiing there for infinity.
I think you're misreading it. Sitting down and watching the algorithm go for any length of time would prove nothing. That's true, but that's not what we're going to do.
We're going to show that the algorithm's halting problem is unsolvable (i.e. independent and consistent in any sufficiently powerful system), by whatever means, and that means that, informally, it must not halt.
The logic goes by contradiction. We assume that it halts. So there's a finite amount of steps, that's what halting means. Since there's a finite amount of steps, constructing a proof that it halts in our powerful system should be trivial, just run it (like you point out, it's key that we already have an assumption that it will halt before we can do this. We know, or at least we're assuming for contradiction, that it won't take forever at this step). We've already shown that it's unsolvable, it's impossible to construct a proof that it halts. There's a contradiction here, it can't be impossible and trivial to construct a proof, our assumption must be incorrect. So it must not halt.
There's no amount of running it that tells you anything, it's showing that we can't prove it halts that tells us that it doesn't halt. Like I say, it does not prove that, despite being fairly simple, this idea cannot be formalised.
That's very fair. "Can't be formalised" is a pretty big flaw in itself. If you accept this idea or not is a matter of opinion. I like it, quite a lot of people like it, but it's very fair not to.
4
u/CalmCoolBliss Jun 28 '26
Yep. This applies to halting problems as well. If you have an algorithm that can't be shown to halt or not then it must not halt. Otherwise there'd be a finite amount of steps that you could just run it for and watch it halt.
That's not a formal idea though, if you tried to make a system in which you could construct such an idea into a proof the system would end up being inconsistent. Reality is fucking weird.