halting problem

Computing Dictionary

halting problem definition


The problem of determining in advance whether a particular program or algorithm will terminate or run forever. The halting problem is the canonical example of a provably unsolvable problem. Obviously any attempt to answer the question by actually executing the algorithm or simulating each step of its execution will only give an answer if the algorithm under consideration does terminate, otherwise the algorithm attempting to answer the question will itself run forever.
Some special cases of the halting problem are partially solvable given sufficient resources. For example, if it is possible to record the complete state of the execution of the algorithm at each step and the current state is ever identical to some previous state then the algorithm is in a loop. This might require an arbitrary amount of storage however. Alternatively, if there are at most N possible different states then the algorithm can run for at most N steps without looping.
A program analysis called termination analysis attempts to answer this question for limited kinds of input algorithm.
(1994-10-20)

The Free On-line Dictionary of Computing, © Denis Howe 2010 http://foldoc.org
Cite This Source
Explore Dictionary.com
Previous Definition: halting
Next Definition: haltless
Words Near: Halting Problem
More from Thesaurus.com
Synonyms and Antonyms for Halting Problem
More from Reference.com
Search for articles containing Halting Problem
More from Dictionary.com Translator
Dictionary.com Word FAQs

Dictionary.com presents 366 FAQs, incorporating some of the frequently asked questions from the past with newer queries.

Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature