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

Latest Computer Science Terms

Related Reading

Margaret Rouse

Margaret Rouse is an award-winning technical writer and teacher known for her ability to explain complex technical subjects to a non-technical, business audience. Over the past twenty years her explanations have appeared on TechTarget websites and she's been cited as an authority in articles by the New York Times, Time Magazine, USA Today, ZDNet, PC Magazine and Discovery Magazine.Margaret's idea of a fun day is helping IT and business professionals learn to speak each other’s highly specialized languages. If you have a suggestion for a new definition or how to improve a technical explanation, please email Margaret or contact her…