Why do we care about termination analysis?

Question

Why is it important to know if a program terminates or not? In particular, what are some consequences of a non-terminating program?

Answer 1

First, the halting problem is the fundamental building block that enables us to prove that many, many problems we care about are undecidable. See https://en.wikipedia.org/wiki/List_of_undecidable_problems.

Second, in some contexts, it is important to know that a program will terminate and in some bounded amount of time. For instance, in an airplane with fly-by-wire, it is important to know that when the pilot presses the left rudder pedal, then the rudder will turn left within a reasonable amount of time. This usually relies on worst-case execution time analysis, which is a bit different from the methods used for solving the halting problem, so I'm not sure whether it is what you are asking about or not. See https://en.wikipedia.org/wiki/Worst-case_execution_time, https://en.wikipedia.org/wiki/Termination_analysis, https://en.wikipedia.org/wiki/Safety-critical_system.

Answer 2

A lot of information processing problems can be modelled as search problems: find a solution within a set. For example, find a number with certain properties (e.g. in numerical analysis or cryptography), or find a point in space with certain properties (e.g. in image processing or robotics), or find a string with certain properties (e.g. in databases), etc.

It is desirable to know whether a solution exists. One way to prove that a solution exists is to write a program that finds a solution. This is an especially nice way to prove the existence of a solution because it's very practical: you can run the program, and you'll get a solution.

How do you know that the program finds a solution? Supposing that the program stops after it prints out a solution (which is what we want in practice, if the goal of the program is to search for a solution), it takes two things:

1. When the program outputs a value, this value is a solution.
2. The program actually does output a value. This means that the program terminates.

In this very common setting, termination distinguishes useful programs from boring ones. Programs that are only useful for their final output are only useful if they terminate. Programs that just do nothing forever are all indistinguishable (as long as you're just interested in their output) and not useful. (Sometimes we're interested in more than a program's final output. But cases where the final output is the only thing that matters are common enough that they're very widely studied.)

As an added benefit, a lot of other interesting properties of programs are equivalent to determining whether a certain modification of the program terminates. For example, “does the function f ever return the value 0?” is equivalent to “does the program function x -> if f(x) = 0 then loop forever”. Another example: “does the program f(); g(); actually execute g()?” is equivalent to “does f() terminate?”, assuming f doesn't call g. Since a lot of questions of the form “does the program P have this property?” are equivalent to “does the program P' terminate”, having theories about program termination is a good basis for theories about all kinds of other useful properties of programs.

Answer 3

It's a fundamental property of any algorithm that it halts after some finite number of steps. Indeed, for many problems, it can be shown that such an algorithm does indeed exist, i.e., that no matter what (valid) input you give, it will always halt. That's a very desirable property just because such procedures are much more useful in practice.