Is non-deterministic running time really so bad?

Question

When I here about the halting problem, it sounds like non-termination is something to avoid and that the halting problem makes it impossible to know if the program/algorithm is good.

But when I think about it, aren't terminating programs the exception and no the rule? I can think of one class of applications where it's expected to terminate in a finite amount of time: compilers. Everything else, from the web-browser I'm using, to the desktop environment, to the text editor, to the shell, to server hosting SO, to the OS itself, aren't supposed to terminate on their own. Heck, even the package manager is supposed to ask the user for confirmation. They're all intended to keep running indefinitely unless a user or sysadmin says otherwise.

My point is is it really so bad that you can't prove that something will terminate? If anything, proving that something will exit in a finite amount of time would be more of a bug than the opposite.

Answer 1

I see your logic but while these programs you mention operate in an infinite loop until terminated you can still terminate them at any time using the exit feature. The problem with non-deterministic termination is that you have no idea when the program will release control of the operation it's performing so that it can be terminated.

Consider this. You write a program it completes a cycle and begins it's loop again. Each cycle would be similar to the program terminating. But rather than closing the program you ask it to start over. If you put a function call to an infinite loop in that program the program holds attention at that function effectively preventing all other functionality until that loop has completed. Hint, never. This is perceived by the user as the program freezing.

Answer 2

Termination of a program is not the point. It's only an easy to explain case of termination of a computation. Here's a practical example:

When you visit a web page, you may start running some Javascript. Depending on how the code is embedded in the page, you may have to wait for this script to terminate before the web page is fully displayed. If the script doesn't terminate within a certain time limit, you'll get a message like this:

(Chrome dialog pictured)

You're supposed to decide somehow whether the script is making progress and will finish if given a little more time, or if it's stuck in an infinite loop. You probably don't know the answer, so you guess. You wait until you're tired of waiting and then give up and kill it, not knowing if it was just 1 more second from completion when you hit the button.

Chrome doesn't tell you that the script is hopelessly stuck and will never terminate because detecting hopelessly stuck scripts would require solving the halting problem.

And it's not just page loads either. Javascript (in the web client context) is event-driven. A function is called when something external happens (i.e. you click on a form submit button) and that event is not processed until the function returns (terminates). A non-terminating script is a big problem.