Halting problem

Halting problem

Dictionary

Tutorials

Encyclopedia

Dictionary

Directory

Dictionary results for: Halting problem

Email this to a friend Halting problem

Halting problem

Source: The Free On-line Dictionary of Computing (27 SEP 03)

	halting problem
     
        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)

Matching Word(s)
Halting