Is the halting problem pointless?

Question

Some programs run quickly, some programs run slowly, and some spend all eternity whirring and whizzing without ever halting. The halting problem uses a thought experiment to prove that there cannot exist a program which can itself examine any arbitrary program and tell the user whether the program being examined will halt.

However, the thought experiment involves programs that were, frankly, designed to act in a way no sane programmer would ever want. Programs that are intentionally designed to halt without producing any useful output, programs that are designed to run indefinitely without halting. As addressed in the answers to the question Is there a subset of programs that avoid the halting problem, the halting problem doesn't apply to all programs. In the extreme case, the following programs would be trivial to analyze:

// Program 1:

while true {}

// Program 2:

print("I really can't tell with this one")

Rather, the halting problem merely indicates that there will always be some programs that can't be analyzed for halting. Those that can be analyzed fall into a certain class of programs that is reasonably well-researched and well-understood, and seems to align quite neatly with the class of useful programs. As for the original proof, while the logic holds, the programs used therein are poor indicators of code a human would actually write, and beg a certain question:

Is it possible that the halting problem only applies to useless programs?

Answer 1

The point of the halting program IMO is not to show that you can't check whether an arbitrary program can halt--that's not a very interesting fact on its own. The point of the halting program, is to use "reduction", to go on and prove that a (very large number of) procedures you might like to have a tool do are also impossible in general:

• Deciding whether two programs are the same (including, whether a program always outputs "true"). This is true even for even many simple definitions of "program".
• Deciding whether a mathematical fact is true or false
• Determining the longest time a program could run
• Checking whether a particular line of code like an error condition, is possible to reach

Of course, much like NP-complete problems, it may still be worthwhile to work on heuristic versions or special cases. But knowing that it's impossible in general, saves us a lot of time trying to come up with a perfect version--after all, we usually want a perfect version if we can get one. And knowing that a problem is impossible in general, is a good hint that it may be hard in specific cases you're likely to run into (checking if two programs are identical for example, is actually really hard in practice).

I think it's fairly reasonable to assume that for any program a human would write, the answer is "yes, it halts"--otherwise it's a bug! So the class of "programs a human would write on purpose" is not really that interesting to look at.

A more interesting question is, "what sorts of things in real programming, lead to problems analyzing whether the program halts?". For example:

• Almost all opcodes (ex. addition) complete
• Bounded loops complete (if the inner loop completes)
• Function calls with no recursion complete (if the body of each function does)
• Arbitrary while loops are hard to analyze
• Global variables may be hard to analyze
• Recursive function calls are hard to analyze

It's quite possible to invent a language (Charity, Epigram, and LOOP are academic/niche langauges, but you can also just imagine making a list of all these features and banning them from Java) where all programs halt. The challenge then becomes, can you express what you want to do in this language?

Edit: For an example of a practical program that is hard to analyze, here is bubble sort in python:

swapped = True
while swapped:
    swapped = False
    for i in range(0, len(list)-1):
        if list[i] > list[i+i]:
            list[i], list[i+i] = list[i+1], list[i]
            swapped = True

As a human, we can tell that this program halts for all inputs. It's much harder to get a computer to realize the same thing.

Answer 2

cf. Hilbert 10th problem and its resolution: determining whether a polynomial has integer roots is equivalent to the halting problem. That'd be an example of a very useful program which has no decidable halting problem, just consider a program that reads a polynomial and returns whether it has integer roots (note that in this setting, where the polynomial is not fixed, the problem is even one level of hardness beyond the halting problem, cf. the arithmetical hierarchy)