[Kranar]

This isn't true in any meaningful way and doesn't really make much sense, it's really just repeating the conclusion of the halting problem in the form of an assumption. Any algorithm that halts will do so, by definition, after a finite amount of time and use a finite amount of space, so saying "assuming unbounded time and memory" is begging the question and taking the conclusion as an assumption.

The very problem is that there is no algorithm that can output whether an arbitrary algorithm on a given input needs unbounded time to begin with.

>if it doesn't [have unbounded range], then it must [terminate], but it is very, very, very hard to determine if that is the case.

This is also false. You can limit the scope of the halting problem to algorithms that have a range of one single input and the halting problem is still undecidable. Heck, you can limit the halting problem to algorithms that don't even take any input whatsoever, they just have a start button and either they halt or do not halt, and that problem is still undecidable. The range has nothing to do with it.

[bruce343434]

Yes it does. This is about turning the computer from a turing machine into a finite automaton. Finite automata can be analyzed for halting in finite time, turing machines can’t. And computers as we know them are not turing machines (which are by definition infinite) but they are state machines, and finite ones at that.

[Kranar]

There is no way to turn a Turing Machine into a finite automaton.

All finite automatons are guaranteed to halt, and do so in linear time. There is nothing to analyze the answer is always true.

[bruce343434]

No but I’m saying: computers are not turing machines because they are not infinite. So they must be finite automata.

[Jerrrry]

exhaustively enumerating all inputs (and thus, outputs) to a program does, without infinite time or memory, turn it into an automaton.

you could then, since having gone over EVERY INPUT...conclude Yes or No, that it Does or Doesn't, HALT.

wtf am i missing

[danielheath]

Taking infinite time to determine whether it halts is not considered a valid answer.

When do you give up and decide it’s not going to terminate? Your answer will be wrong for any program which simply waits one second longer.

[Jerrrry]

that part is understood.

a dripping faucet, for example - is it dripping at 10 drips per hour? or 5 drips per hour? did it stop dripping? no way to tell - the period between drops could be one moment longer than you observed - it could had dripped right after you stopped observing it.

this upper limit is called the busy beaver function. but it is only applicable to turing machines, which we don't build, because we don't have an infinite tape.