Don't miss an insight. Subscribe to Techopedia for free.


Halting Problem

What Does Halting Problem Mean?

The halting problem, commonly applied to Turing-complete programs and models, is the problem of finding out whether, with the given input, a program will halt at some time or continue to run indefinitely. The halting problem is an early example of a decision problem, and also a good example of the limits of determinism in computer science.


Techopedia Explains Halting Problem

In general, the halting problem is often used in an abstract capacity to explain why it may be impossible to decide whether a program will ever run indefinitely, or not. Experts explain how halting analysis for a given computer requires a significantly larger and more powerful computer, and how halting analysis for a program of any significant size requires large-dimensional numbers that would occupy massive memory spaces.

Others struggling with the nature of the halting problem point to analysis of indefinite loops or the idea that programmers can isolate halting results using non-Turing-complete programs or particular computer language structures. Some computer scientists and mathematicians suggest that the halting problem is useful as guidance for any number of other types of programming analysis, or as a decisive method for explaining computer programming limitations to the less savvy stakeholders.


Related Terms