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.

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

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

wtf am i missing

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.

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.

This is useful. Verifiers which work by symbolic execution examine large numbers of cases they work through the control flow. Each case can contain a large number of states; you only need one case for each control flow pattern. Now, some programs run into combinatorial explosion when you do that. The number of cases to be examined grows rapidly. That means halting detection is NP-hard, not impossible. There's a difference.

The Microsoft Static Driver Verifier operates on the assumption that if symbolic execution doesn't terminate after a reasonable amount of automatic analysis, your driver doesn't get to run in the kernel. This is a good, practical solution.

ETA: wait that doesn't make sense because it's equivalent to computing the busy beaver number for the program under consideration. What am I missing?

[1] I'm aware there's no unique BB sequence, I don't know that the rigorous phrasing is.

Yes. There's even a practical way to check if a finite deterministic machine has repeated a previous state. Run two of them in parallel, in lockstep so that one takes two steps while the other takes one. If they ever have identical state, they're in a loop. This takes 1.5x the compute power plus 2x as much memory, so it's far cheaper than storing all previous states.

(Some early mainframe era educational interpreter supposedly did this, to stop simple student infinite loops quickly in a batch system.)

Here's a paper on the busy beaver problem which discusses upper bounds.[1] The key here is that the upper bound on states is not computable. However, if you force an upper bound by limiting memory, it becomes computable. But really hard. That paper discusses how very rapidly the number of states grows for that problem.

[1] https://homepages.hass.rpi.edu/heuveb/Teaching/Logic/CompLog...

A ton of useful stuff (for instance in compiler optimizers) can be done with deciding between "trivial to prove it terminates" vs. "who knows, this instance of the problem is hard! I'll just skip this optimization in this ridiculously non-representatively rare case."

  You say that you are not being pedantic,
  So why does that make me feel so frantic?

  If we need unbounded ranges and time,
  Is that in your lifetime, or possibly mine?

  Someday we have to compare all our notes,
  So none will have learned it only by rote.

If you’re only concerned with physically realizable computing: the number of states can easily become too large to be analyzable.