0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ "the halting problem doesn't apply to all programs" That is not what is said in the link. $\endgroup$ – plop Oct 14 at 19:22
  • 1
    $\begingroup$ Your question implicitly assumes that the undecidability result regarding the halting problem is some sort of property of individual programs. It isn't, it is a property of the collection of programs as a whole and the property of halting or not, which divides them into two sets. It is the nature of that partition, what makes the halting problem undecidable. There are certainly useful and useless programs in both sides of that partition. $\endgroup$ – plop Oct 14 at 20:00
  • 2
    $\begingroup$ Welcome to COMPUTER SCIENCE @SE. Avoid questions [where answers] are primarily opinion-based, or that are likely to generate discussion rather than answers. $\endgroup$ – greybeard Oct 14 at 21:43
  • $\begingroup$ If the halting problem had absolutely no relevance to practical programming goals (though it does as Z.Vance's answer explains), it would be a mathematical fact that would still be very important for other reasons. (I could list the reasons, but that process would not halt before I had to do something else, which makes the listing task infinite in a practical sense from my point of view. :-) $\endgroup$ – Mars Oct 14 at 22:25
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The paragraph that starts "I think it's fairly reasonable ..." is not. Lots of programs that a human would write don't halt by design: List all primes, list all Fibonacci numbers, display the current time, control the traffic lights, ... $\endgroup$ – plop Oct 15 at 2:40
  • $\begingroup$ "I think it's fairly reasonable to assume ..." is incorrect. Sure, most business applications are designed to halt, but a lot of computational resources are used for things like searching for mathematical proofs or counter-examples to conjectures. It'd be rather nice to be able to write a simple program that naively tests a conjecture on every value and halts on a counter-example, and then quickly get an answer by asking the halting oracle whether the conjecture test halts or not (and the oracle can tell us the conjecture is true or false, while the naive test can only say it is false). $\endgroup$ – Extrarius Oct 23 at 19:02
0
$\begingroup$

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)

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.